結果
問題 | No.2857 Div Array |
ユーザー |
|
提出日時 | 2024-08-25 15:01:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 592 ms / 2,000 ms |
コード長 | 1,846 bytes |
コンパイル時間 | 3,768 ms |
コンパイル使用メモリ | 291,616 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 15:01:49 |
合計ジャッジ時間 | 9,106 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;using ll = long long;using mint = modint998244353;template<class T>class Matrix{private:int ro, co;vector<vector<T>> vec;public:Matrix(): Matrix(0, 0) {}Matrix(const int _ro, const int _co, const T _e=0):ro(_ro), co(_co), vec(_ro, vector<T>(_co, _e)) {}int row() const { return ro; }int col() const { return co; }vector<T> operator[](int i) const {return vec[i];}vector<T> &operator[](int i){return vec[i];}Matrix<T> &operator*=(const Matrix<T> &rhs){assert(ro==co && rhs.row()==rhs.col() && co==rhs.col());return *this = (*this)*rhs;}Matrix<T> operator*(const Matrix<T> &rhs) const {assert(co==rhs.row());Matrix<T> res(ro, rhs.col());for(int i=0; i<ro; i++){for(int j=0; j<rhs.col(); j++){for(int k=0; k<co; k++){res[i][j] += vec[i][k]*rhs[k][j];}}}return res;}Matrix<T> pow(long long n) const {assert(ro==co);Matrix<T> res(ro, co);for(int i=0; i<ro; i++){res[i][i] = 1;}Matrix<T> x = *this;while(n){if(n&1) res *= x;x *= x;n >>= 1;}return res;}};int main(){ll N;cin >> N;int M, K;cin >> M >> K;map<int,int> cnt;for(int i=1; i<=M; i++){int d = M/i;cnt[d]++;}vector<int> comp;for(auto [key,val]:cnt){comp.emplace_back(key);}int siz = comp.size();Matrix<mint> mat(siz, siz);for(int i=0; i<siz; i++){for(int j=0; j<siz; j++){if(abs(comp[i]-comp[j])<=K){mat[i][j] = cnt[comp[i]];}}}Matrix<mint> vec(siz, 1);for(int i=0; i<siz; i++){vec[i][0] = cnt[comp[i]];}auto dp = mat.pow(N-1)*vec;mint ans = 0;for(int i=0; i<siz; i++){ans += dp[i][0];}cout << ans.val() << endl;return 0;}