結果
問題 | No.2857 Div Array |
ユーザー | ku_senjan |
提出日時 | 2024-08-25 15:01:39 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 592 ms / 2,000 ms |
コード長 | 1,846 bytes |
コンパイル時間 | 3,768 ms |
コンパイル使用メモリ | 291,616 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-25 15:01:49 |
合計ジャッジ時間 | 9,106 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 11 ms
6,944 KB |
testcase_11 | AC | 438 ms
6,944 KB |
testcase_12 | AC | 80 ms
6,940 KB |
testcase_13 | AC | 23 ms
6,940 KB |
testcase_14 | AC | 418 ms
6,944 KB |
testcase_15 | AC | 32 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 348 ms
6,940 KB |
testcase_18 | AC | 296 ms
6,940 KB |
testcase_19 | AC | 146 ms
6,940 KB |
testcase_20 | AC | 574 ms
6,944 KB |
testcase_21 | AC | 592 ms
6,940 KB |
testcase_22 | AC | 576 ms
6,940 KB |
testcase_23 | AC | 558 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 1 ms
6,940 KB |
testcase_29 | AC | 1 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; template<class T> class Matrix{ private: int ro, co; vector<vector<T>> vec; public: Matrix(): Matrix(0, 0) {} Matrix(const int _ro, const int _co, const T _e=0): ro(_ro), co(_co), vec(_ro, vector<T>(_co, _e)) {} int row() const { return ro; } int col() const { return co; } vector<T> operator[](int i) const { return vec[i]; } vector<T> &operator[](int i){ return vec[i]; } Matrix<T> &operator*=(const Matrix<T> &rhs){ assert(ro==co && rhs.row()==rhs.col() && co==rhs.col()); return *this = (*this)*rhs; } Matrix<T> operator*(const Matrix<T> &rhs) const { assert(co==rhs.row()); Matrix<T> res(ro, rhs.col()); for(int i=0; i<ro; i++){ for(int j=0; j<rhs.col(); j++){ for(int k=0; k<co; k++){ res[i][j] += vec[i][k]*rhs[k][j]; } } } return res; } Matrix<T> pow(long long n) const { assert(ro==co); Matrix<T> res(ro, co); for(int i=0; i<ro; i++){ res[i][i] = 1; } Matrix<T> x = *this; while(n){ if(n&1) res *= x; x *= x; n >>= 1; } return res; } }; int main(){ ll N; cin >> N; int M, K; cin >> M >> K; map<int,int> cnt; for(int i=1; i<=M; i++){ int d = M/i; cnt[d]++; } vector<int> comp; for(auto [key,val]:cnt){ comp.emplace_back(key); } int siz = comp.size(); Matrix<mint> mat(siz, siz); for(int i=0; i<siz; i++){ for(int j=0; j<siz; j++){ if(abs(comp[i]-comp[j])<=K){ mat[i][j] = cnt[comp[i]]; } } } Matrix<mint> vec(siz, 1); for(int i=0; i<siz; i++){ vec[i][0] = cnt[comp[i]]; } auto dp = mat.pow(N-1)*vec; mint ans = 0; for(int i=0; i<siz; i++){ ans += dp[i][0]; } cout << ans.val() << endl; return 0; }