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;
	}
}