結果
問題 | No.2857 Div Array |
ユーザー | ayataka5 |
提出日時 | 2024-08-25 16:40:14 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,870 bytes |
コンパイル時間 | 3,208 ms |
コンパイル使用メモリ | 256,880 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 16:40:19 |
合計ジャッジ時間 | 4,924 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long mod = 998244353; template< typename T > vector< pair< pair< T, T >, T > > quotient_range(T N) { T M; vector< pair< pair< T, T >, T > > ret; for(M = 1; M * M <= N; M++) { ret.emplace_back(make_pair(M, M), N / M); } for(T i = M; i >= 1; i--) { T L = N / (i + 1) + 1; T R = N / i; if(L <= R && ret.back().first.second < L) ret.emplace_back(make_pair(L, R), N / L); } return ret; } using ll = long long; using mat = vector<vector<long long>>; /// 行列積 mat mat_mul(mat &a, mat &b) { mat res(a.size(), vector<ll>(b[0].size())); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b[0].size(); j++) { for (int k = 0; k < b.size(); k++) { (res[i][j] += a[i][k] * b[k][j]) %= mod; } } } return res; } /// 行列累乗 mat mat_pow(mat a, long long n) { mat res(a.size(), vector<ll>(a.size())); // 単位行列で初期化 for (int i = 0; i < a.size(); i++) res[i][i] = 1; // 繰り返し二乗法 while (n > 0) { if (n & 1) res = mat_mul(a, res); a = mat_mul(a, a); n >>= 1; } return res; } int main() { int N, M, K; cin >> N >> M >> K; auto range = quotient_range(M); int k(size(range)); mat dp(1, vector<long long>(k)); for(int i = 0; i < k; i++) { dp[0][i] = (range[i].first.second - range[i].first.first + 1); } mat P(k, vector<long long>(k)); for(int i = 0; i < k; i++) { for(int j = 0; j < k; j++) { if(K < abs(range[i].second-range[j].second)) continue; P[i][j] = (range[j].first.second - range[j].first.first + 1); } } P = mat_pow(P, N-1); dp = mat_mul(dp, P); long long ans(0LL); for(int i = 0; i < k; i++) { ans = (ans + dp[0][i]) % mod; } cout << ans << endl; return 0; }