Submission #2277433

---

Source Code Expand

#include <iostream>
using namespace std;
const int mod = 1000000007;
int n, d, s, a, inv[33], dp[33][33][909];
int binpow(int val, int ex) {
	int ret = 1;
	while(ex) {
		if(ex & 1) ret = 1LL * ret * val % mod;
		val = 1LL * val * val % mod;
		ex >>= 1;
	}
	return ret;
}
int main() {
	inv[1] = 1;
	for(int i = 2; i <= 30; i++) inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;
	cin >> n >> d; dp[0][0][0] = 1;
	for(int i = 0; i < n; i++) {
		cin >> a;
		for(int j = 0; j <= i; j++) {
			for(int k = 0; k <= s; k++) {
				dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % mod;
				int val = 1;
				for(int l = 0; l < a; l++) {
					dp[i + 1][j + 1][k + l] = (dp[i + 1][j + 1][k + l] + 1LL * dp[i][j][k] * val) % mod;
					val = 1LL * val * (d - k - l) % mod * inv[l + 1] % mod;
				}
			}
		}
		s += a;
	}
	int ret = 0;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= d && j <= s; j++) {
			int val = 1LL * dp[n][i][j] * binpow(n - i, d - j) % mod;
			if(i % 2 == 0) ret = (ret + val) % mod;
			else ret = (ret - val + mod) % mod;
		}
	}
	cout << ret << endl;
	return 0;
}

Submission Info

Judge Result