Submission #1837934

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
int d[333];
const int M=1000000007;
int f[2][333][666];
int fac[333];
int invf[333];
int ex(int b,int e)
{
	int ans=1;
	for(;e;e>>=1,b=(long long)b*b%M)
		if(e&1)ans=(long long)ans*b%M;
	return ans;
}
int main()
{
	int n=io::F();
	for(register int i=1;i<=n;++i)d[i]=io::F();
	fac[0]=1;
	for(register int i=1;i<=n;++i)fac[i]=(long long)fac[i-1]*i%M;
	int fl=1;
	for(register int i=1;i<=n;++i)if(d[i]!=2)fl=0;
	if(fl)
	{
		printf("%lld\n",fac[n-1]*(long long)(M+1>>1)%M);
		return 0;
	}
	invf[n]=ex(fac[n],M-2);
	for(register int i=n-1;i>=0;--i)invf[i]=(i+1)*(long long)invf[i+1]%M;
	int(*x)[666]=f[0],(*y)[666]=f[1];
	f[0][0][0]=1;
	for(register int i=1;i<=n;++i,std::swap(x,y))
	{
		for(register int j=0;j<=i;++j)
			for(register int k=0;k<=n+n;++k)
			{
				y[j][k]=x[j][k]*(long long)invf[d[i]-1]%M;
				if(d[i]>=2&&j>=1&&k+2>=d[i])y[j][k]=(y[j][k]+x[j-1][k-d[i]+2]*(long long)invf[d[i]-2])%M;				
			}
	}
	#define register
	int ans=0;
	for(register int i=3;i<n;++i)
		for(register int j=1;j<=n+n;++j)
			ans=(ans+(long long)x[i][j]*fac[n-i-1]%M*fac[i-1]%M*invf[j-1]%M*invf[2]%M*fac[j]%M)%M;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result