Submission #3010200

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 305;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

int n, d[MAXN];
lint fact[MAXN], invf[MAXN];
lint dp[MAXN][MAXN][MAXN];

lint f(int x, int y, int z){
	if(x == n) return (y == 0 && z == 0);
	if(y < 0 || z < 0) return 0;
	if(~dp[x][y][z]) return dp[x][y][z];
	lint ans = f(x + 1, y, z);
	if(d[x] > 1) ans += f(x + 1, y - 1, z - (d[x] - 2)) * (d[x] - 1);
	ans %= mod;
	return dp[x][y][z] = ans;
}

int main(){
	fact[0] = 1;
	for(int i=1; i<MAXN; i++) fact[i] = fact[i-1] * i % mod;
	for(int i=0; i<MAXN; i++) invf[i] = ipow(fact[i], mod-2);
	cin >> n;
	for(int i=0; i<n; i++) cin >> d[i];
	if(count(d, d + n, 2) == n){
		cout << fact[n-1] * ipow(2, mod - 2) % mod<< endl;
		return 0;
	}
	memset(dp, -1, sizeof(dp));
	lint ret = 0;
	for(int i=3; i<=n; i++){
		for(int j=1; j<=n; j++){
			lint ans = fact[n - 1 - i] * fact[i - 1] % mod;
			ans *= j;
			ans %= mod;
			ans *= f(0, i, j);
			ans %= mod;
			ret += ans;
		}
	}
	ret %= mod;
	for(int j=0; j<n; j++) ret *= invf[d[j] - 1], ret %= mod;
	ret %= mod;
	ret *= (mod + 1) / 2;
	cout << ret % mod << endl;
}

Submission Info

Judge Result