なるほど…。
https://yukicoder.me/problems/no/2484
問題
4要素の整数列Aがある。初期状態で全部の値は0である。
以下のいずれかの処理を、計M回任意の順で行える。
- 何もしない
- Aの全要素をインクリメントする
- Aの先頭要素かをインクリメントする
- Aの末尾要素かをインクリメントする
最終的なAの値が与えられたとき、そのようなAを構成できる処理の手順は何通りか。
解法
処理のうち、A[1]とA[3]をインクリメントする回数xを総当たりしよう。
そうすると、
a. A[1]もA[3]もインクリメントしない
b. A[1]はインクリメントするがA[3]はインクリメントしない。この時A[0]も確定でインクリメントする。
c. A[3]はインクリメントするがA[1]はインクリメントしない
d. A[1]もA[3]もインクリメントする。この時A[2]も確定でインクリメントする
Aの値から、a,b,c,dの数が確定する。まずこれらの並びを定めよう。
- b以外でA[0]をインクリメントするのは、a,dのパターンのいずれか
- d以外でA[2]をインクリメントするのは、b,cのパターンのいずれか
いずれも二項係数で数え上げられる。
int N,M; int B[2020]; const ll mo=998244353; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { 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; } if(C_<0 || C_>N_) return 0; return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>B[i]; ll ret=0; for(int p24=0;p24<=min(B[1],B[3]);p24++) { int p2=B[1]-p24; int p4=B[3]-p24; int p0=M-p2-p4-p24; ll pat=comb(M,p24)*comb(M-p24,p2)%mo*comb(M-p24-p2,p4)%mo; pat=pat*comb(p0+p24,B[0]-p2)%mo; pat=pat*comb(p2+p4,B[2]-p24)%mo; ret+=pat; } cout<<ret%mo<<endl; }
まとめ
言われれば簡単だけど、うまく思いつけないな…。