結果
問題 |
No.2857 Div Array
|
ユーザー |
![]() |
提出日時 | 2025-10-02 13:42:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 1,825 bytes |
コンパイル時間 | 7,288 ms |
コンパイル使用メモリ | 334,096 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-02 13:42:52 |
合計ジャッジ時間 | 9,589 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <bitset> #include <set> #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vmi = vector<mint>; using vvmi = vector<vmi>; using vvvmi = vector<vvmi>; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) vvmi mat(const vvmi &a, const vvmi &b, int len){ vvmi res(len, vmi(len)); rep(i, len)rep(j, len){ mint tmp = mint(0); rep(k, len)tmp += a[i][k]*b[k][j]; res[i][j] = tmp; } return res; } int main(){ int n, m, k; cin >> n >> m >> k; set<int> st; rep2(i, 1, m+1)st.insert(m/i); vi id; for(auto i : st)id.push_back(i); vi cnt(m+1, 0); rep2(i, 1, m+1)cnt[m/i]++; int len = id.size(); vvmi base(len, vmi(len, mint(0))); rep(i, len)rep(j, len){ if(abs(id[i] - id[j]) <= k)base[i][j] = mint(cnt[id[i]]); } vvvmi matrix; matrix.push_back(base); rep(i, 31){ int l = matrix.size(); matrix.push_back(mat(matrix[l-1], matrix[l-1], len)); } vvmi e(len, vmi(len, mint(0))); rep(i, len)e[i][i] = mint(1); bitset<32> bs(n-1); rep(i, 32){ if(bs[i])e = mat(e, matrix[i], len); } vmi ft(len); rep(i, len)ft[i] = mint(cnt[id[i]]); mint ans = mint(0); rep(i, len){ rep(j, len){ ans += e[i][j] * ft[j]; } } cout << ans.val() << endl; return 0; }