Fより簡単だと思った。
https://codeforces.com/contest/1942/problem/G
問題
以下のカードがある。
- スペシャルカードが5枚
- draw 0 カードがA枚
- draw 1 カードがB枚
- draw 2 カードがC枚
カードの山から5枚とり、以下の手順を行う。
- 手持ちのdraw xカードを1枚すて、カードの山の上からx枚とる。
- 手持ちのカードにスペシャルカード5枚集まったら勝ち。手持ちのdraw xカードがなくなった場合に、スペシャルカードが5枚揃わなかったら負け。
カードの山の並び(A+B+C+5)!通りのうち、勝ちパターンとなる確率を求めよ。
解法
まず、draw 1カードは無視して考える。最後にB枚を適当に挿入すればよい。
draw xカードがなくなるまでにdraw 2カードを取る回数を総当たりする。
この時、draw 2カードの配置は、カタラン数の要領で計算できる。
その時、draw 0カードとスペシャルカードを取れる枚数の合計が決まるので、その中にスペシャルカード5枚が入る確率を求めればよい。
int T,A,B,C; const ll mo=998244353; const int NUM_=2400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll comb(ll N_, ll C_) { if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } ll catalan_arrange(int X,int Y,int T=1) { if(X+T<=Y) return 0; return (comb(X+Y,Y)-comb(X+Y,Y-T)+mo)%mo; } ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);} ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; cin>>T; while(T--) { cin>>A>>B>>C; A+=5; //ダメな確率を求める ll ret=0; FOR(i,C+1) { //何枚draw 2 cardを取るか ll pat=catalan_arrange(i,4+i,5); // draw0中に5枚入る確率 ll a=comb(i+5,0)*comb(A-(i+5),5)+comb(i+5,1)*comb(A-(i+5),4)+comb(i+5,2)*comb(A-(i+5),3)+comb(i+5,3)*comb(A-(i+5),2)+comb(i+5,4)*comb(A-(i+5),1); (pat*=a%mo)%=mo; //残りのカード (ret+=pat*comb(A+C-(i+5+i),C-i)%mo)%=mo; } //B毎の挿入 ret=ret*hcomb(A+C+1,B)%mo; ret=ret%mo*fact[A-5]%mo*fact[5]%mo*fact[B]%mo*fact[C]%mo*factr[A+B+C]%mo; ret=(1+mo-ret)%mo; cout<<ret<<endl; } }
まとめ
まぁまぁ時間かかってるな。