結果
問題 | No.2468 Mercurialist |
ユーザー |
![]() |
提出日時 | 2023-08-13 01:54:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 2,000 ms |
コード長 | 1,202 bytes |
コンパイル時間 | 3,114 ms |
コンパイル使用メモリ | 248,108 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-11-20 18:57:36 |
合計ジャッジ時間 | 4,783 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; #include<atcoder/modint> using mint = atcoder::modint998244353; const int mx = 3<<17; mint fac[mx+1],ifac[mx+1]; int main(){ fac[0] = 1; for(int i = 1;i<=mx;i++) fac[i] = fac[i-1] * mint::raw(i); ifac[mx] = fac[mx].inv(); for(int i = mx-1;i>=0;i--) ifac[i] = ifac[i+1] * mint::raw(i+1); int x,y,z,k; cin>>x>>y>>z>>k; int all = x + y + z; int ni = 1; mint ans = 0; while(true){ int die = ni + k + 1; int can = y + z; if(die-1>can) break; int left = ni - y; left = max(left,0); if(left>z) break; mint tmp = ifac[all] * fac[all-(die-1)]; tmp *= fac[z] * ifac[z-left]; int use = ni - left; assert(use<=y); int res = z - left + 1; res += y - use; assert(res-1>=0); tmp *= mint::raw(res).pow(use) - mint::raw(res-1).pow(use); int r = y + z - use - left; assert(r>=k); int used = left + use; int will = die - 1 - used; tmp *= fac[r] * ifac[r-will]; ans += tmp; ni++; } ans = 1 - ans; cout<<ans.val()<<endl; }