結果
問題 | No.2936 Sum of Square of Mex |
ユーザー |
|
提出日時 | 2024-10-12 06:30:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 945 bytes |
コンパイル時間 | 5,649 ms |
コンパイル使用メモリ | 317,208 KB |
実行使用メモリ | 12,324 KB |
最終ジャッジ日時 | 2024-10-12 06:30:52 |
合計ジャッジ時間 | 7,976 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using mint=atcoder::modint998244353; mint fac[200009],fac2[200009]; mint ifac[200009]; int main(){ int n,m;cin>>n>>m; //事前計算 fac[0]=1;for(int i=0;i<n;i++)fac[i+1]=(i+1)*fac[i]; for(int i=0;i<=n;i++)ifac[i]=fac[i].inv(); fac2[0]=1;for(int i=0;i<n;i++)fac2[i+1]=(m+1-i)*fac2[i]; //第二種スターリング数の計算 vector<mint> f(n+1),g(n+1); for(int i=0;i<=n;i++){ f[i]=mint(i).pow(n)*ifac[i]; g[i]=(i&1?-1:1)*ifac[i]; } vector<mint> Stirling=convolution(f,g); //_{M+1}C_{r} を求める auto comb=[&](int r)->mint { if(r<0||m+1<r)return 0; return fac2[r]*ifac[r]; }; mint ans=0; //種類数をiと決め打ち for(int i=1;i<=min(n,m+1);i++){ mint tmp=0; tmp+=comb(i)*i*i; tmp-=comb(i-1)*(2*i-1)*(m-i+1); tmp+=comb(i-2)*(m-i+1)*(m-i+2); ans+=fac[i]*Stirling[i]*tmp; } cout<<ans.val()<<endl; }