天下一プログラマーコンテスト2013 決勝 D - 天下一ボディービルコンテスト

包除原理🤤

問題

高橋くんにはn個の筋肉があり、これからd日間毎日トレーニングをする
高橋くんは毎日筋肉を1つ選んでトレーニングしてその筋肉を1kg増やす
またi番目の筋肉は最低でもa[i]kgは増やすという目標がある
n個全ての目標を達成するようなトレーニングスケジュールは何通りあるか

1 <= n <= 30
1 <= d <= 10^9
1 <= a[i] <= 30

解法

「全ての目標を達成」の余事象は「1つ以上の目標を達成しない」になる
f(S): 少なくとも集合Sに含まれる目標は全て達成しないようなトレーニングスケジュールの個数
とすると、答えは包除原理より
Σ f(S) * (-1)^|S|
となる

達成しない目標の集合Sとしては空集合を除いた2^n - 1個ある
まともに計算するのはきついからdpでうまく状態をまとめたい
dp[i][j][k]: i番目まででj個の目標を選び、それらを全て達成しないように計k回のトレーニングを割り振るような場合の数
とすると、j個以上の目標を達成しないようなトレーニングスケジュールの個数は、
Σ dp[n][j][k] * (k回のトレーニングをd日のうちどこに配置するか)
* (残りd-k日を選ばなかったn-j個の筋肉に適当に割り振る組み合わせ)
= Σ dp[n][j][k] * dCk * (n-j)^(d-k) (0 <= k <= Σa[])
というふうに求められる
故に答えは Σ ↑ * (-1)^(j)

dpの遷移は以下の通り

(i番目の目標は考慮しない場合)
dp[i+1][j][k] += dp[i][j][k]

(i番目の目標を考慮に入れる場合)
i番目の筋肉をL (0 <= L < a[i]) 回鍛えるとして、
dp[i+1][j+1][k+L]
+= dp[i][j][k] * (既にあるj個のトレーニングの列の隙間j+1個に重複ありでL個入れる)
= dp[i][j][k] * (j+1)H(L)

実装

dがクソデカいからdCkがちょっとめんどい
事前にdcinit()でテーブルを作っておく
分子と分母をメモしながらkを1増やしていき、(分子)*(分母の逆元) で求めてる(フェルマーの小定理)

dが絡まない組み合わせの数は俺の好きなパスカルの三角形☺️

#define int long long

int n, d, a[33], dp[33][33][1010], pa[1010][1010], dcomb[1010], res;

int comb(int n, int r) {
	if (r<0 || r>n) return 0;
	if (r==0) return 1;
	if (pa[n][r]) return pa[n][r];
	return pa[n][r] = (comb(n-1, r-1) + comb(n-1, r)) %mod;
}

void dcinit() {
	dcomb[0] = 1;
	int num = 1, den = 1;
	reps(i,1,1010) {
		(num *= d-i+1) %= mod;
		(den *= i) %= mod;
		dcomb[i] = num * mop(den,mod-2) %mod;
	}
}

signed main() {
	cin >> n >> d;
	rep(i,n) cin >> a[i];
	dp[0][0][0] = 1;
	rep(i,n) rep(j,n) rep(k,1010) if (dp[i][j][k]) {
		(dp[i+1][j][k] += dp[i][j][k]) %= mod;
		rep(l,a[i]) (dp[i+1][j+1][k+l] += dp[i][j][k] * comb(k+l,l)) %= mod;
	}
	dcinit();
	rep(i,n+1) rep(j,min(1010ll,d+1))
		(res += dp[n][i][j] * dcomb[j] %mod * mop(n-i,d-j) * (i%2 ? -1 : 1)) %= mod;
	(res += mod) %= mod;
	cout << res << endl;
}

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_d