一种典型的组合数DP
f[i][j]表示前i种数值排列有j个不合法间隙的方案数
然后枚举第i个分成几块k 有l块塞入j个不合法空隙中进行转移
答案即为f[n][0]
不过还要乘以排列数
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define cl(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=55; const ll P=1e9+7; int n; int cnt[N],sum[N]; ll dp[N][555]; ll C[555][555],fac[555]; inline void Pre(){ C[0][0]=1; for (int i=1;i<=500;i++){ C[i][0]=1; for (int j=1;j<=i;j++) (C[i][j]=C[i-1][j-1]+C[i-1][j])%=P; } fac[0]=1; for (int i=1;i<=500;i++) fac[i]=fac[i-1]*i%P; } int main(){ int T,test=0; freopen("t.in","r",stdin); freopen("t.out","w",stdout); Pre(); read(T); while (T--){ read(n); for (int i=1;i<=n;i++) read(cnt[i]),sum[i]=sum[i-1]+cnt[i]; dp[1][cnt[1]-1]=1; for (int i=2;i<=n;i++) for (int j=0;j<=sum[i-1]+1;j++) if (dp[i-1][j]) for (int k=1;k<=cnt[i];k++) for (int l=0;l<=k;l++) (dp[i][j-l+cnt[i]-k]+=dp[i-1][j]*C[j][l]%P*C[sum[i-1]+1-j][k-l]%P*C[cnt[i]-1][k-1]%P)%=P; ll ret=dp[n][0]; for (int i=1;i<=n;i++) ret*=fac[cnt[i]],ret%=P; printf("Case %d: %lld\n",++test,ret); cl(dp); } return 0; }
