結果
問題 |
No.2857 Div Array
|
ユーザー |
![]() |
提出日時 | 2024-08-25 15:11:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,711 bytes |
コンパイル時間 | 1,228 ms |
コンパイル使用メモリ | 88,336 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 15:11:30 |
合計ジャッジ時間 | 2,370 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
//floor(M / i) の値の種類は 2 sqrt(M) 個くらいなので、行列累乗すればOK #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <atcoder/modint> #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; using namespace atcoder; using mint = modint998244353; typedef pair<int, int> P; typedef vector<mint> Vec; typedef vector<Vec> Mat; Vec mul(Mat a, Vec b) { Vec ret(a.size()); for (int i = 0; i < a.size(); i++) { mint c = 0; for (int j = 0; j < b.size(); j++) { c += a[i][j] * b[j]; } ret[i] = c; } return ret; } Mat mul(Mat a, Mat b) { int n = a.size(); int m = b[0].size(); Mat ret(n, Vec(m)); int i, j, k; rep(i, n) { rep(j, m) { rep(k, b.size()) { ret[i][j] += a[i][k] * b[k][j]; } } } return ret; } Mat ident(int sz) { Mat ret(sz, Vec(sz)); int i; rep(i, sz) ret[i][i] = 1; return ret; } Mat powmod(Mat a, int n) { if (n == 0) return ident(a.size()); if (n % 2 == 0) return powmod(mul(a, a), n / 2); return mul(a, powmod(a, n - 1)); } signed main() { int i, j; int n, m, K; cin >> n >> m >> K; vector<int> cnts(m + 1); for (i = 1; i <= m; i++) cnts[m / i]++; vector<P> valCnt; for (i = 1; i <= m; i++) { if (cnts[i] == 0) continue; valCnt.push_back(P(i, cnts[i])); } int sz = valCnt.size(); Mat mat(sz, Vec(sz)); rep(i, sz) { rep(j, sz) { if (abs(valCnt[i].first - valCnt[j].first) > K) continue; // i --> j mat[j][i] = valCnt[j].second; } } Mat matMul = powmod(mat, n - 1); Vec initV(sz); rep(i, sz) initV[i] = valCnt[i].second; Vec vec = mul(matMul, initV); mint ans = 0; rep(i, sz) ans += vec[i]; cout << ans.val() << endl; return 0; }