hdu_4532 湫秋系列故事——安排座位

题目:

   为了给腾讯公司找到更多优秀的人才,HR湫秋最近去某高校组织了一次针对该校所有系的聚会,邀请了每个系的一些优秀学生来参加。
   作为组织者,湫秋要安排他们的座位。这并不是一件很简单的事情,因为只有一排位置,并且位置总数恰好等于参加聚会的人数。为了促进交流,两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法(任意两个合理的安排方法,只要有一个位置的同学不同,都被认为是不同的)。

思路:

   先约定把两个同系的人坐在一起叫做一个冲突对。
   如果直接考虑把每个人存进dp状态,那么状态多达。既然不能存进状态,那就考虑每次把一整个系的人加入,设表示现在计算到第个系,已经有个冲突对的方案数。每次加入一个系时,只要计算破坏了多少个冲突对,新增了多少个冲突对。枚举个间隔,有个会破坏冲突对,把这个系的人分成组,新产生的对数就是为这个系的人数),算出这个情况的方案数即可(就是一个组合加整数拆分应该还是好算的吧。。。)。

代码:

#include <bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i=(a),i##_END_=(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i=(a),i##_END_=(b);i>=i##_END_;i--)
typedef long long ll;
const int mod=1e9+7;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);y-=a/b*x;
}
int inv(int a){
    ll x,y;
    exgcd(a,mod,x,y);
    return (x%mod+mod)%mod;
}
int fac[505],invfac[505];
void init(){
    fac[0]=1;
    rep(i,1,500)fac[i]=(ll)fac[i-1]*i%mod;
    invfac[500]=inv(fac[500]);
    drep(i,499,0)invfac[i]=(ll)invfac[i+1]*(i+1)%mod;
}
inline int C(int x,int y){
    return (ll)fac[x]*invfac[y]%mod*invfac[x-y]%mod;
}
int a[50],sum[50],dp[50][500];
int main(){
    init();
    int cas,n;
    scanf("%d",&cas);
    rep(t,1,cas){
        scanf("%d",&n);
        rep(i,1,n)scanf("%d",a+i);
        rep(i,1,n)sum[i]=sum[i-1]+a[i];
        clr(dp,0);
        dp[1][a[1]-1]=fac[a[1]];
        rep(k,1,n-1)
            rep(x,0,sum[k]){
                int d=sum[k]+1-x;
                rep(i,0,x){
                    rep(j,0,d){
                        if(i+j>a[k+1])break;
                        int las=a[k+1]-i-j;
                        (dp[k+1][x-i+las]+=(ll)dp[k][x]*C(x,i)%mod*C(d,j)%mod*C(a[k+1]-1,i+j-1)%mod*fac[a[k+1]]%mod)%=mod;
                    }
                }
            }
        printf("Case %d: %d\n",t,dp[n][0]);
    }
    return 0;
}