http://tenka1-2013-final.contest.atcoder.jp/tasks/tenka1_2013_final_d
包除原理の良問です。
目標を達成しないスケジュールを考えます。それはどれかの筋肉が目標を達成しなければいいです。
なのでS:=目標を達成しない筋肉の集合、f(S):=Sについて何通りあるか で包除原理をすればいいです。
しかし|S|<=30なので単純にやると間に合わないので、|S|が同じものをまとめてdpで計算します。
すると計算量はO(N^3*max(A)^2)とかになって間に合います。
いろいろ混乱してコードであれこれしていたらサンプルがあってしまった…って感じです。
なぜかトレーニング一切しない筋肉はSに加えていいかで混乱した。もちろん目標を達成していないので加えてよいです。
あと|S|=|N|の時は自由にトレーニングできる筋肉がないため、場合分けが必要です。ここを忘れて最初2ケースだけ落ちた。
int N, D; ll fac[MAX_N], inv[MAX_N], fiv[MAX_N]; //fiv:inv(fac(i)) ll mod_pow(ll a, ll n) { if(n == 0) return 1; ll res = mod_pow(a, n / 2); if(n % 2 == 0) return res * res % mod; else return a * res % mod * res % mod; } ll invf(ll a) { return mod_pow(a, mod - 2); } void C_init(int n) { fac[0] = fac[1] = 1; inv[1] = 1; fiv[0] = fiv[1] = 1; rep(i, 2, n + 1) { fac[i] = fac[i - 1] * i % mod; inv[i] = mod - inv[mod % i] * (mod / i) % mod; fiv[i] = fiv[i - 1] * inv[i] % mod; } } ll C(int a, int b) { //assume a >= b if(a < b || a < 0 || b < 0) return 0; return fac[a] * fiv[b] % mod * fiv[a - b] % mod; } ll getC(ll a, ll b) { ll res = 1; rep(i, 0, b) MUL(res, (a - i)); return res * fiv[b] % mod; } int A[50]; ll dp[50][50][1000]; void solve() { C_init(2000); cin >> N >> D; rep(i, 0, N) cin >> A[i]; dp[0][0][0] = 1; rep(i, 0, N) { rep(j, 0, N) { rep(k, 0, 1000) { if(!dp[i][j][k]) continue; ADD(dp[i + 1][j][k], dp[i][j][k]); rep(l, 0, A[i]) { ADD(dp[i + 1][j + 1][k + l], dp[i][j][k] * C(k + l, l) % mod); } } } } ll ans = 0; rep(i, 0, N + 1) { rep(j, 0, 1000) { ll tmp; if(i == N) { if(j != D) continue; tmp = dp[N][i][j]; } else tmp = dp[N][i][j] * mod_pow(N - i, D - j) % mod * getC(D, j) % mod; if(i % 2 == 1) ADD(ans, mod - tmp); else ADD(ans, tmp); } } cout << ans << "\n"; }