一道典型的组合问题，可惜当时想的做法就不对，一直走到黑了。当时想的做法是用容斥做，可惜当时容斥的姿势不对，首先先把问题看成是组合问题最后再转化为排列，枚举每组是否出现挨着的，枚举到头求组合，由于可能统计重复，所以容斥。这种思想明显漏算了很多情况，当时还脑残的认为肯定正确……。
想了半天都没想到怎么做，于是去膜拜大神的BLOG去了，虽然只有精简的几行，而且没看懂具体怎么做的，不过思路瞬间成竹在胸了。
正解用组合DP做，因为状态能够递推，还是先把排列问题转化成组合问题，最后再乘各组的阶乘。解决组合类问题的思想其实还是那几种，插空、捆绑、隔板什么的。
设dp[i][j]为第i组人员加入到队列中后，有j个空的两边是同一组的人。
那么枚举i-1组 j所有的状态j，枚举当前组有k个空是左右人同组的(捆绑或隔板)，枚举这几个人插入了j`中的几个空l(插空)。
这样新的j的状态就是j+k-l，状态也就可以转移了。
View Code
1 #include <map> 2 #include <set> 3 #include <list> 4 #include <queue> 5 #include <stack> 6 #include <cmath> 7 #include <ctime> 8 #include <vector> 9 #include <bitset> 10 #include <cstdio> 11 #include <string> 12 #include <numeric> 13 #include <cstring> 14 #include <cstdlib> 15 #include <iostream> 16 #include <algorithm> 17 #include <functional> 18 using namespace std; 19 typedef long long ll; 20 #define Exp 1e-8 21 #define inf 0x7fffffff 22 #define read freopen("in.txt","r",stdin) 23 #define write freopen("out.txt","w",stdout) 24 #define maxn 55 25 #define mod 1000000007 26 ll num[maxn]; 27 ll dp[maxn][505]; 28 ll muti_mod(ll a,ll b,ll n) 29 { 30 ll exp=a%n,res=0; 31 while(b) 32 { 33 if(b&1){res+=exp;if(res>=n)res-=n;} 34 exp<<=1; 35 if(exp>=n)exp-=n; 36 b>>=1; 37 } 38 return res; 39 } 40 ll con[505][505],mul[maxn]; 41 void init() 42 { 43 memset(con,0,sizeof(con)); 44 con[0][0]=1; 45 for(int i=1;i<505;i++) 46 { 47 con[i][0]=con[i][i]=1; 48 for(int j=1;j<i;j++)con[i][j]=(con[i-1][j-1]+con[i-1][j])%mod; 49 } 50 mul[0]=1; 51 for(int i=1;i<maxn;i++)mul[i]=muti_mod(mul[i-1],i,mod); 52 } 53 int main() 54 { 55 //read; 56 init(); 57 int cas,n; 58 scanf("%d",&cas); 59 for(int x=1;x<=cas;x++) 60 { 61 scanf("%d",&n); 62 for(int i=1;i<=n;i++)scanf("%I64d",&num[i]); 63 memset(dp,0,sizeof(dp));dp[0][0]=1; 64 ll sum=0,m=1; 65 for(int i=1;i<=n;i++) 66 { 67 ll t=num[i]; 68 for(int j=0;j<=sum;j++)if(dp[i-1][j]) 69 { 70 for(int k=1;k<=t;k++) 71 for(int l=0;l<=j&&l<=k;l++) 72 { 73 ll tmp=dp[i-1][j]*con[t-1][k-1]%mod*con[j][l]%mod*con[sum+1-j][k-l]%mod; 74 dp[i][j+(t-k)-l]=(dp[i][j+(t-k)-l]+tmp)%mod; 75 } 76 } 77 sum+=num[i],m=muti_mod(m,mul[t],mod); 78 } 79 ll ans=muti_mod(dp[n][0],m,mod); 80 printf("Case %d: %I64d\n",x,ans); 81 } 82 return 0; 83 }