結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-27 17:19:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 2,181 bytes |
コンパイル時間 | 2,816 ms |
コンパイル使用メモリ | 211,956 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-27 17:20:04 |
合計ジャッジ時間 | 3,996 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using ll = std::int64_t;using T = std::tuple<int, int, int>;using Matrix = std::vector<std::vector<ll>>;const ll MOD = 998244353;Matrix matPow(Matrix A, int n){auto d = A.size();Matrix R(d, std::vector<ll>(d, 0));for(int i=0;i<d;i++){R[i][i] = 1;}while(n > 0){if(n & 1){Matrix M(d, std::vector<ll>(d, 0));for(int i=0;i<d;i++){for(int j=0;j<d;j++){for(int k=0;k<d;k++){M[i][j] += R[i][k] * A[k][j] % MOD;if(M[i][j] >= MOD){M[i][j] -= MOD;}}}}R = std::move(M);}Matrix M(d, std::vector<ll>(d, 0));for(int i=0;i<d;i++){for(int j=0;j<d;j++){for(int k=0;k<d;k++){M[i][j] += A[i][k] * A[k][j] % MOD;if(M[i][j] >= MOD){M[i][j] -= MOD;}}}}A = std::move(M);n /= 2;}return R;}int main(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);int N, M, K;std::cin >> N >> M >> K;std::vector<int> Q, L, R;{int q = 1;int l = M / (q + 1);int r = M / q;while(true){Q.emplace_back(q);L.emplace_back(l);R.emplace_back(r);if(q == M){break;}q = M / l;l = M / (q + 1);r = M / q;}}Matrix T(Q.size(), std::vector<ll>(Q.size(), 0ll));for(int i=0;i<Q.size();i++){int l = std::lower_bound(std::begin(Q), std::end(Q), Q[i] - K) - std::begin(Q);int r = std::upper_bound(std::begin(Q), std::end(Q), Q[i] + K) - std::begin(Q);for(int j=l;j<r;j++){T[i][j] = (R[i] - L[i]) % MOD;}}Matrix TK = matPow(T, N - 1);ll res = 0;for(int i=0;i<Q.size();i++){for(int j=0;j<Q.size();j++){res += TK[i][j] * (R[j] - L[j]) % MOD;if(res >= MOD){res -= MOD;}}}std::cout << res << std::endl;}