bzoj4665 小w的喜糖（dp+容斥）

4665: 小w的喜糖

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 222 Solved: 130
[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

首先我们把每颗糖（第i种糖有$A_i$个）都看成不同的（也就是同种糖的排列顺序不同也算进方案）

最后再$ans/=A_i!$，这样就可以忽略同种糖的问题

一般看到这种题，都是先套路地求至少有$i$个......的方案数，再用容斥求答案。本题也是如此

我们套路地设$f[i][j]$为前$i$种糖，至少$j$个人不合法的方案数

$f[i][j]=sum_{k=0}^{min(j,A_i)} f[i-1][j-k]*C(A_i,k)*A_i!/(A_i-k)!$

对于每个$f[n][i]$，剩下的$n-i$个人可以随意分糖

所以最终方案数$F[i]=f[n][i]*(n-i)!$

但是肯定有重复算的鸭

所以搞搞容斥统计下就好辣

$ans=sum_{i=0}^n(-1)^iF[i]$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 2005
const ll P=1e9+9;
int n,A[N];
ll f[N][N],inv[N],fac[N],ifac[N],ans;
void prep(){
    inv[1]=1; fac[0]=fac[1]=ifac[0]=ifac[1]=1;
    for(ll i=2;i<=n;++i){
        inv[i]=(P-P/i)*inv[P%i]%P;
        fac[i]=fac[i-1]*i%P;
        ifac[i]=ifac[i-1]*inv[i]%P;
    }
}
inline ll C(int a,int b){return fac[a]*ifac[b]%P*ifac[a-b]%P;}
int main(){
    scanf("%d",&n); prep();
    for(int i=1,q;i<=n;++i) scanf("%d",&q),++A[q];
    f[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j)
            for(int k=0;k<=min(j,A[i]);++k)
                f[i][j]=(f[i][j]+f[i-1][j-k]*C(A[i],k)%P*fac[A[i]]%P*ifac[A[i]-k]%P)%P;
    for(int i=0;i<=n;++i) ans=((ans+1ll*((i&1)?-1:1)*f[n][i]*fac[n-i]%P)%P+P)%P;
    for(int i=1;i<=n;++i) if(A[i]>0) ans=ans*ifac[A[i]]%P;
    printf("%lld",ans);
    return 0;
}