[组合数学][计数DP]JZOJ 4254 集体照

2024-02-24 23:17:34

Description

一年一度的高考结束了，我校要拍集体照。本届毕业生共分n个班，每个班的人数为Ai。这次拍集体照的要求非常奇怪：所有学生站一排，且相邻两个学生不能同班。现在，安排这次集体照的老师找到了你，想问问你一共有多少种方案。方案数可能很大，最终结果对1,000,000,007取模。

Input

输入文件名为photo.in。
第一行为为一个整数n。
第二行为n个正整数，分别为每个班的人数。

Output

输出文件photo.out，共1行，为总方案数。

Sample Input

输入1：
2
1 2
输入2：
2 
1 3
输入3：
3 
1 2 3

Sample Output

输出1：
2
输出2：
0
输出3：
120

Data Constraint

对于30%，Sigma(Ai) <=10
对于另外10%，n=2
对于另外20%，n=3
对于100%，1<=n<=50,1<=Ai<=50, Sigma(Ai)<=1500

分析

组合数学题日常博客跳转

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5e2+10;
const int Sigma=1.5e3+10;
const ll P=1e9+7;
int n;
ll a[N],s[N],fact[N],C[Sigma][Sigma],f[N][Sigma];

int main() {
    freopen("photo.in","r",stdin);freopen("photo.out","w",stdout);
    scanf("%d",&n);
    fact[0]=C[0][0]=1;
    for (int i=1;i<N;i++) fact[i]=fact[i-1]*i%P;
    for (int i=1;i<Sigma;i++)
        for (int j=0;j<=i;j++)
            C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    f[1][s[1]-1]=1;
    for (int i=2;i<=n;i++)
        for (int j=0;j<=s[i-1];j++)
            if (f[i-1][j])
                for (int k=1;k<=a[i];k++)
                    for (int t=0;t<=min(k,j);t++)
                        (f[i][j+a[i]-k-t]+=f[i-1][j]*C[j][t]%P*C[a[i]-1][k-1]%P*C[s[i-1]+1-j][k-t]%P)%=P;
    for (int i=1;i<=n;i++) (f[n][0]*=fact[a[i]])%=P;
    printf("%lld\n",f[n][0]);
}

View Code

码农公寓