ARC102 E - Stop. Otherwise...
問題
1〜kが等確率で出るk面サイコロをn個振る
2 <= i <= 2kに対して、どの異なる2つのサイコロの出目の和もiにならないような出目の組の場合の数を求めよ
ただしサイコロ同士は区別しない
1 <= k <= 2000
2 <= n <= 2000
解法
どの2つの出目の和もtにならない組の個数を求めたい
これは a+b = t となる各(a,b)について、どちらか一方が現れない or 両方とも現れなければいい
(ただしtが偶数のときはk/2が1個以下しか現れないという条件も付く)
(a,b)の組の個数をxとし、どちらか一方が現れる組の個数をyとすると、答えは
(xからy個取る組み合わせの数) * (y組それぞれでどちらの数が現れるようにするか) * (残りn-y個の出目をk-2x+y個から重複を許して選ぶ組み合わせの数)
だけ増える (tが奇数のとき)
tが偶数でもk/2が0個現れる場合と1個現れる場合で2通り考えるだけ
これを1 <= y <= xの全てのyでやればいい
実装
comb(n,r): nCr
hcomb(n,r): nHr
signed main() { p[0] = 1; reps(i,1,2020) p[i] = p[i-1]*2 %mod; cin >> k >> n; reps(i,2,k*2+1) { ll x = 0, res = 0; reps(a,1,k+1) if (a<i-a && i-a<=k) x++; rep(y,x+1) { if (i%2==0) (res += comb(x,y)*p[y] %mod *(hcomb(k-x*2-1+y,n-y) + hcomb(k-x*2-1+y,n-y-1)) %mod) %= mod; else (res += comb(x,y)*p[y] %mod *hcomb(k-x*2+y,n-y) %mod) %= mod; } cout << res << endl; } }