結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:35:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 2,310 ms |
コンパイル使用メモリ | 211,668 KB |
最終ジャッジ日時 | 2025-02-24 01:12:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder//modint>using mint = atcoder::modint998244353;using mat = vector<vector<mint>>;mat mat_prod(mat A, mat B) {int N = A.size();int M = B[0].size();int K = A[0].size();mat C(N, vector<mint>(M));for(int i = 0; i < N; i++) {for(int j = 0; j < M; j++) {for(int k = 0; k < K; k++) {C[i][j] += A[i][k] * B[k][j];}}}return C;}mat mat_pow(mat A, int n) {int N = A.size();mat C(N, vector<mint>(N));for(int i = 0; i < N; i++) {C[i][i] = 1;}while(n) {if(n & 1) C = mat_prod(C, A);A = mat_prod(A, A);n /= 2;}return C;}int main() {int N, M, K;cin >> N >> M >> K;map<int, int> mp;for(int x = 1; x <= M; x++) {mp[M / x]++;}vector<pair<int, int>> v(mp.begin(), mp.end());const int L = v.size();mat dp_coef(L, vector<mint>(L));for(int i = 0; i < L; i++) {// cout << v[i].first << " " << v[i].second << endl;for(int j = 0; j < L; j++) {if(abs(v[i].first - v[j].first) <= K) {dp_coef[j][i] = v[j].second;}}}mat dp_init(L, vector<mint>(1));for(int i = 0; i < L; i++) {dp_init[i][0] = v[i].second;}mat dp_res = mat_prod(mat_pow(dp_coef, N - 1), dp_init);mint ans = 0;for(int i = 0; i < L; i++) {ans += dp_res[i][0];}cout << ans.val() << endl;}