結果
問題 | No.1655 123 Swaps |
ユーザー |
![]() |
提出日時 | 2021-06-25 02:49:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 1,153 bytes |
コンパイル時間 | 3,471 ms |
コンパイル使用メモリ | 158,400 KB |
最終ジャッジ日時 | 2025-01-22 11:48:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <iostream> #include <vector> #include <atcoder/all> using namespace std; using namespace atcoder; const int MOD=924844033; using mint=static_modint<MOD>; mint f[600060], invf[600060]; void fac(int n){ f[0]=1; for(int i=1; i<=n; i++) f[i]=f[i-1]*i; invf[n]=f[n].inv(); for(int i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1); } mint comb(int x, int y){ if(!(0<=y && y<=x)) return 0; return f[x]*invf[y]*invf[x-y]; } int main() { int a, b, c; cin>>a>>b>>c; int n=a+b+c; if(n%2!=0){ cout<<0<<endl; return 0; } fac(n); mint w=mint(5).pow((MOD-1)/3), winv=w.inv(); mint s1=f[n]*invf[a]*invf[b]*invf[c], s2=0; vector<mint> vp(a+1), vq(b+1); mint wp=winv.pow(a); for(int i=0; i<=a; i++){ vp[i]=f[n/2]*invf[i]*invf[a-i]*wp; wp*=winv; } wp=w.pow(b); for(int i=0; i<=b; i++){ vq[i]=f[n/2]*invf[i]*invf[b-i]*wp; wp*=w; } auto v=convolution(vp, vq); for(int i=max(0, a+b-n/2); i<=n/2 && i<v.size(); i++){ s2+=v[i]*invf[n/2-i]*invf[n/2-a-b+i]; } mint ans=(s1+2*s2)/3; cout<<ans.val()<<endl; return 0; }