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
1
1
2
2
3
3
Sample Output
10
HINT
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~DP+容斥原理~
首先每个人拿的颜色的顺序对答案并没有影响，所以我们可以把同种颜色的人分成一块，按块处理。
用f[i][j]表示前i个人，其中有j个人不满足条件的方案数，那么我们就可以DP后容斥，+0-1+2-3...
每次DP时，我们枚举这一组数中有多少还是自己（即不满足），然后乘上挑出这些人的方案数（组合数），再除以剩余的人的排列方式数（因为这些人相当于是同样的）（逆元，预处理出来还可以用来求组合数，比较快~），最后统计答案的时候还要乘上满足要求的人的排列数。
注意乘的时候要强制转化为long long！这次是快速幂里面少加了！
模数是10^9+9不是10^9+7！
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mod 1000000009
#define ll long long
#define kkk(u) (u&1 ? -1:1)int n,ans,tot,col[2001],sheng[2001],ni[2001],f[2001][2001];int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int mi(int u,int v)
{int now=1;for(;v;v>>=1,u=(ll)u*u%mod) if(v&1) now=(ll)now*u%mod;return now;
}void init()
{sheng[0]=1;for(ll i=1;i<=n;i++) sheng[i]=(ll)sheng[i-1]*i%mod;ni[n]=mi(sheng[n],mod-2);for(ll i=n-1;~i;i--) ni[i]=(ll)ni[i+1]*(i+1)%mod;
}int cc(int n,int m)
{return n<m ? 0:(ll)sheng[n]*ni[n-m]%mod*ni[m]%mod;
}void add(int &a,int b)
{a+=b;while(a<0) a+=mod;while(a>=mod) a-=mod;
}int main()
{n=read();init();f[0][0]=1;for(int i=1;i<=n;i++) col[read()]++;for(int i=1;i<=n;i++){for(int j=0;j<=tot;j++)for(int k=0;k<=col[i];k++) add(f[i][j+k],(ll)f[i-1][j]*cc(col[i],k)%mod*ni[col[i]-k]%mod);tot+=col[i];}for(int i=0;i<=tot;i++) add(ans,(ll)kkk(i)*f[n][i]*sheng[tot-i]%mod);printf("%d\n",ans);return 0;
}