题链：

题解：

容斥，dp

令 v[i] 表示原来拥有i类糖果的人数。

(一个套路，首先把每个糖果看成互不相同的,(最后再来除以 v[i]!，把同种糖果看成相同的) )

定义 dp[i][j]表示前i类糖果，有j个人的糖果和原来的一样，其他 N-j 个人暂时不拿糖果的方案数。

这个的转移如下：

对于已经确定的 i,j,枚举一个 k表示原来拥有的是第i类糖果的k个人任然拿到的是第i类糖果。

${dp[i][j]=dp[i-1][j-k]}\times{

{C}_{v[i]}^{k}}\times{v[i]}\times{(v[i]-1)}\times{…}\times{(v[i]-k+1)}$

式子后面乘的东西意思是那k个人在第i类糖果中的选择方法数(每个糖果看成不一样的了) 。

然后就再把每一个 dp[N][i] * (N-i)! 表示剩下的人就随便选择糖果。

此时 dp[N][i]的含义即为:重新分配糖果后，至少有 i个人拿到了原来的那类糖果的方法数。

然后就是考虑容斥，答案 ANS=dp[N][0]-dp[N][1]+dp[N][2]-dp[N][3]......

最后还要把同类糖果看成相同的东西，即 ANS/=v[i]。

代码：

#include
    
     #include
     
      #include
      
       #define MAXN 2500#define _ %mod#define filein(x) freopen(#x".in","r",stdin)#define fileout(x) freopen(#x".out","w",stdout)using namespace std;const int mod=1000000009;int v[MAXN],dp[MAXN][MAXN],C[MAXN][MAXN],fac[MAXN],inv[MAXN];int N,ANS;int pow(int a,int b){	int now=1;	while(b){		if(b&1) now=(1ll*now*a)_;		a=(1ll*a*a)_; b>>=1;	}	return now;}int main(){	scanf("%d",&N); 	fac[0]=inv[0]=1;	for(int i=1;i<=N;i++) fac[i]=(1ll*fac[i-1]*i)_;	inv[N]=pow(fac[N],mod-2);	for(int i=N-1;i>=1;i--) inv[i]=(1ll*inv[i+1]*(i+1))_;	for(int i=0;i<=N;i++){		C[i][0]=1;		for(int j=1;j<=i;j++)			C[i][j]=(1ll*C[i-1][j-1]+C[i-1][j])_;	}	for(int i=1,x;i<=N;i++) scanf("%d",&x),v[x]++;	dp[0][0]=1;	for(int i=1;i<=N;i++)		for(int j=0;j<=N;j++)			for(int k=0;k<=v[i];k++){				if(k>j) break;				dp[i][j]=(1ll*dp[i][j]+1ll*dp[i-1][j-k]*C[v[i]][k]_*fac[v[i]]_*inv[v[i]-k])_;			}	for(int i=0;i<=N;i++){		dp[N][i]=1ll*dp[N][i]*fac[N-i]_;		if(i&1) dp[N][i]=(1ll*dp[N][i]*(-1)+mod)_;		ANS=(1ll*ANS+dp[N][i]+mod)_;	}	for(int i=1;i<=N;i++) ANS=1ll*ANS*inv[v[i]]_;	printf("%d",ANS);	return 0;}