結果
問題 | No.2857 Div Array |
ユーザー |
|
提出日時 | 2024-09-03 22:26:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 4,545 bytes |
コンパイル時間 | 1,781 ms |
コンパイル使用メモリ | 141,148 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-03 22:26:56 |
合計ジャッジ時間 | 3,560 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include<iostream>#include<string>#include<queue>#include<vector>#include<cassert>#include<random>#include<set>#include<map>#include<cassert>#include<unordered_map>#include<bitset>#include<numeric>#include<algorithm>using namespace std;typedef long long ll;const int inf=1<<30;const ll INF=1LL<<62;typedef pair<int,ll> P;typedef pair<int,P> PP;const ll MOD=998244353;const int dy[]={0,1,0,-1};const int dx[]={1,0,-1,0};const int mod = 998244353;struct mint {long long x; // typedef long long long long;mint(long long x=0):x((x%mod+mod)%mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}mint operator+(const mint a) const { return mint(*this) += a;}//後ろのconstはメンバxを変更しないことを示すmint operator-(const mint a) const { return mint(*this) -= a;}mint operator*(const mint a) const { return mint(*this) *= a;}bool operator==(const mint a) const {return a.x==x;}mint pow(unsigned long long int t) const {assert(t>=0);if (!t) return 1;//aがtで割り切れない場合には t%=(mod-1)をして良いmint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const { return pow(mod-2);}mint& operator/=(const mint a) { return *this *= a.inv();}mint operator/(const mint a) const { return mint(*this) /= a;}};std::istream& operator>>(std::istream& is, mint& a) { return is >> a.x;}std::ostream& operator<<(std::ostream& os, const mint& a) { return os << a.x;}struct combination {std::vector<mint> fact, ifact;combination(int n):fact(n+1),ifact(n+1) {assert(n < mod);fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n-k];}};vector<vector<mint>> mat(vector<vector<mint>> A,vector<vector<mint>> B){//A*Bint h=A.size(),w=A[0].size();int t=B[0].size();vector<vector<mint>> C(h,vector<mint>(t));for(int i=0;i<h;i++){for(int j=0;j<t;j++){mint ans=0;for(int k=0;k<w;k++){ans = (ans + A[i][k]*B[k][j]);}C[i][j] = ans;}}return C;}//行列xのy乗vector<vector<mint>> multi_matrix(vector<vector<mint>>x, ll y ){int h=x.size();vector<vector<mint>> pow(h,vector<mint>(h));for(int i=0;i<h;i++) pow[i][i]=1;//単位行列while(y>0){if(y&1){pow = mat(pow,x);}y = y>>1;x = mat(x,x);}return pow;}template <class T> struct compress{std::set<T> st;std::map<T,int> mp;std::map<int,T> inv_mp;int sz;compress(const std::vector<T>& a):sz(0){for(auto x:a){st.insert(x);}for(auto x:st){mp[x]=sz++;}for(auto x:st){inv_mp[mp[x]]=x;}}int val(const T& x){//ベクトルaの要素xに対応した要素を取り出すreturn mp[x];}int size(){return sz;}};int main(){ll N,M,K;cin>>N>>M>>K;vector<int> cc;cc.push_back(0);for(int i=1;i<=M;i++){cc.push_back(M/i);}map<int,int> mp;for(int i=1;i<=M;i++){mp[M/i]++;}compress<int> CC(cc);cc.clear();for(auto x:mp){cc.push_back(x.first);}int l=cc.size();vector<int> vs(l);for(int i=0;i<l;i++){vs[i]=cc[i];}vector<int> cnt(l,0);for(int i=0;i<l;i++){cnt[i]=mp[vs[i]];}vector<vector<mint>> A(l,vector<mint>(l));for(int i=0;i<l;i++){for(int j=0;j<l;j++){if(abs(vs[i]-vs[j])<=K){//xからtへの遷移があるA[i][j]+=cnt[i];}}}auto res = multi_matrix(A,N-1);// for(int i=0;i<N;i++){// vector<mint> ndp(M+1,0);// swap(dp,ndp);// }mint ans=0;for(int i=0;i<l;i++){for(int j=0;j<l;j++){ans+=res[i][j]*cnt[j];}}cout<<ans<<endl;}