天下一プログラマーコンテスト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