結果
問題 | No.2105 Avoid MeX |
ユーザー |
![]() |
提出日時 | 2022-10-21 23:08:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,479 bytes |
コンパイル時間 | 612 ms |
コンパイル使用メモリ | 68,936 KB |
最終ジャッジ日時 | 2025-02-08 10:22:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 WA * 2 |
other | AC * 14 WA * 5 |
ソースコード
#include <iostream> using namespace std; using ll = long long; const int MX = 400010; ll f[MX],inv[MX],fi[MX]; constexpr ll mod = 998244353; void solve(){ inv[1] = 1; for(int i=2;i<MX;i++){ inv[i] = mod - (mod/i)*inv[mod%i]%mod; } f[0] = fi[0] = 1; for(int i=1;i<MX;i++){ f[i] = f[i-1]*i%mod; fi[i] = fi[i-1]*inv[i]%mod; } } ll nck(ll n, ll k){ if(n<0 || k<0 || n<k) return 0; return f[n]*fi[k]%mod*fi[n-k]%mod; } ll pw(ll a,ll x){ ll ret = 1; while(x){ if(x&1) (ret *= a) %= mod; (a *= a) %= mod; x /= 2; } return ret; } ll dp[2010][2010] = {}; int main(){ int i,j,c,x; cin >> c >> x; solve(); if(x==0){ if(c>0) cout << inv[c + 1] << endl; else cout << 0 << endl; } else if(c>=x){ cout << inv[x] << endl; return 0; }else{ dp[0][0] = 1; int las = 0; for(i=1;i<=2000;i++){ if(c + i>x) break; for(j=0;j<=x;j++){ dp[i][j] = inv[c + i]*j%mod*dp[i - 1][j]%mod; if(j && (c + i + 1 - j)>=0) dp[i][j] += inv[c + i]*(c + i + 1 - j)%mod*dp[i - 1][j - 1]%mod; } las = i; } ll ans = 0; // for(j=0;j<=x;j++){ // cout << inv[x - j + 1] << " " << dp[las][j] << endl; // } for(j=0;j<=x;j++) (ans += inv[x - j + 1]*dp[las][j]%mod) %= mod; cout << (mod + 1 - ans)%mod << "\n"; } }