bzoj4665小w的喜糖 dp+容斥

4665: 小w的喜糖

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 120 Solved: 72
[Submit][Status][Discuss]

Description

废话不多说，反正小w要发喜糖啦！！

小w一共买了n块喜糖，发给了n个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

Input

第一行，一个整数n

接下来n行，每行一个整数，第i个整数Ai表示开始时第i个人手中的糖的种类

对于所有数据，1≤Ai≤k,k<=N,N<=2000

Output

一行，一个整数Ans，表示方案数模1000000009

Sample Input

6
1
1
2
2
3
3

Sample Output

f[i][j]表示前i种糖,j个人拿到的糖相同,剩下的糖果先不发给人
转移式还是挺好推的
把每种糖看成不同,b[i]表示第i种糖的个数
每新增加一种糖,枚举现在几个人拿到自己的糖一个人拿到自己的糖要在所有同种糖中选择
转移完之后,所有f[i][j]*=fac[n-j]表示剩下的糖随意分给其他人,不保证不分到自己的糖
所以f[i][j]就变成了至少j个人拿到相同的糖,容斥一下
最后,因为把每种糖的个体视为不同,需要 /fac[b[i]]
推荐blog
http://www.cnblogs.com/zj75211/p/8035076.html

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 2005

#define mod 1000000009

using namespace std;

int n,m,f[N][N],a[N],b[N],fac[N],inv[N],c[N][N],sum[N];

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

    scanf("%d",&a[i]);

    sort(a+1,a+1+n);

    for(int i=1;i<=n;i++){

        if(a[i]!=a[i-1])m++;

        b[m]++;

    }

    for(int i=1;i<=m;i++)

    sum[i]=sum[i-1]+b[i];

    for(int i=0;i<=2000;i++)

    c[i][i]=c[i][0]=1;

    for(int i=1;i<=2000;i++)

    for(int j=1;j<i;j++)

    c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

    fac[0]=fac[1]=inv[0]=inv[1]=1;

    for(int i=2;i<=2000;i++){

        fac[i]=1ll*fac[i-1]*i%mod;

        inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;

    }

    for(int i=2;i<=2000;i++)inv[i]=1ll*inv[i]*inv[i-1]%mod;

    f[0][0]=1;

    for(int i=1;i<=m;i++)

    for(int j=0;j<=sum[i-1];j++)

    for(int k=0;k<=b[i];k++)

    f[i][j+k]=(f[i][j+k]+1ll*f[i-1][j]*c[b[i]][k]%mod*fac[b[i]]%mod*inv[b[i]-k]%mod)%mod;

    ll ans=0;

    for(int i=n;i>=0;i--)

    ans=(ans+1ll*((n-i)&1?-1:1)*f[m][i]*fac[n-i])%mod;

    for(int i=1;i<=m;i++)ans=ans*inv[b[i]]%mod;

    ans<0?ans+=mod:1;

    cout<<ans;

    return 0;

}

秒客网