結果
問題 | No.2857 Div Array |
ユーザー |
![]() |
提出日時 | 2024-08-28 22:10:53 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 2,511 bytes |
コンパイル時間 | 13,075 ms |
コンパイル使用メモリ | 280,516 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-28 22:11:16 |
合計ジャッジ時間 | 7,032 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i, n) for(int i=0;i<(n);++i)#define rep1(i, n) for(int i=1;i<=(n);i++)#define ll long longusing mint = modint998244353;using P = pair<ll,ll>;using lb = long double;using T = tuple<ll, ll, ll>;#ifdef LOCAL# include <debug_print.hpp># define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define dbg(...) (static_cast<void>(0))#endif// Coodinate Compression// https://youtu.be/fR3W5IcBGLQ?t=8550template<typename T=long long>struct CC {bool initialized;vector<T> xs;CC(): initialized(false) {}void add(T x) { xs.push_back(x);}void init() {sort(xs.begin(), xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end());initialized = true;}int operator()(T x) {if (!initialized) init();return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;}T operator[](int i) {if (!initialized) init();return xs[i];}int size() {if (!initialized) init();return xs.size();}};template<typename T>struct Matrix {int h, w;vector<vector<T>> d;Matrix() {}//初期化のときは Matrix<> a(h, w)Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}Matrix& unit() {assert(h == w);rep(i,h) d[i][i] = 1;return *this;}const vector<T>& operator[](int i) const { return d[i];}vector<T>& operator[](int i) { return d[i];}Matrix operator*(const Matrix& a) const {assert(w == a.h);Matrix r(h, a.w);rep(i,h)rep(k,w)rep(j,a.w) {r[i][j] += d[i][k]*a[k][j];}return r;}//Matcix<> newa = a.pow(k)と使うMatrix pow(long long t) const {assert(h == w);if (!t) return Matrix(h,h).unit();if (t == 1) return *this;Matrix r = pow(t>>1);r = r*r;if (t&1) r = r*(*this);return r;}};int main(){int n, m, k;cin >> n >> m >> k;CC cc;cc.add(0);for(int i=1;i<=m;i++) {cc.add(m/i);}map<int, int> mp;for(int i=1;i<=m;i++) {mp[m/i]++;}int l = cc.size();vector<int> vs(l);rep(i,l) vs[i] = cc[i];Matrix<mint> M(l, l);vector<int> cnt(l);rep(i,l) cnt[i] = mp[vs[i]];dbg(cnt, vs);rep(i,l)rep(j,l) {if(abs(vs[i]-vs[j])<=k) M[i][j]+=cnt[i];}auto ret = M.pow(n-1);mint ans = 0;rep(i,l) rep(j,l) ans += ret[i][j]*cnt[j];cout << ans.val() << endl;return 0;}