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

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