Submission #1870259

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 300
#define E2 500000004ll
#define MOD 1000000007
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define Outc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
template <typename T> inline void Out(T x)
{
	if(!x){Outc('0'); return;} if(x < 0) Outc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; Outc(*--_Ot)); if(_O-_Ob >= BUF_SIZE-50) _END;
}
int f[305][305][605], d[305], fac[605], efac[605], n, N, ans; bool flag = true;
inline int fastpow(int s, int n){int a = 1; for(; n; n&1 ? a = 1ll*a*s%MOD : 0, s = 1ll*s*s%MOD, n >>= 1); return a;}
int main()
{
	n = read(), N = n<<1; for(rint i = 1; i <= n; flag &= (d[i++]=read())==2);
	fac[0] = 1; for(rint i = 1; i <= N; fac[i] = 1ll*i*fac[i-1]%MOD, i++);
	efac[N] = fastpow(fac[N],MOD-2); for(rint i = N; i; efac[i-1] = 1ll*i*efac[i]%MOD, i--); f[0][0][0] = 1;
	for(rint i = 1, j, k; i <= n; i++)
		for(j = 0; j <= i; j++)
			for(k = 0; k <= N; k++)
				f[i][j][k] = f[i-1][j][k], j&&d[i]>=2&&k>=d[i]-2 ? f[i][j][k] = (f[i][j][k]+1ll*(d[i]-1ll)*f[i-1][j-1][k-(d[i]-2)])%MOD : 0;
	for(rint j = 3, k; j < n; j++)
		for(k = 1; k <= N; ans = (ans+1ll*fac[n-j-1]*fac[j-1]%MOD*k%MOD*f[n][j][k])%MOD, k++);
	for(rint i = 1; i <= n; ans = 1ll*ans*efac[d[i]-1]%MOD, i++); ans = E2*ans%MOD, flag ? ans = (ans+E2*fac[n-1])%MOD : 0, printf("%d\n",ans); return 0;
}

Submission Info

Judge Result