4665: 小w的喜糖
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 94 Solved: 53Description
废话不多说，反正小w要发喜糖啦！！小w一共买了n块喜糖，发给了n个人，每个喜糖有一个种类。这时，小w突发奇想，如果这n个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。Input
第一行，一个整数n接下来n行，每行一个整数，第i个整数Ai表示开始时第i个人手中的糖的种类对于所有数据，1≤Ai≤k,k<=N,N<=2000Output
一行，一个整数Ans，表示方案数模1000000009Sample Input
6
1
1
2
2
3
3Sample Output
10HINT
Source
【分析】
DP+容斥类的题目都不是很会做啊QWQ。
人不分顺序，同一种糖果要一起做。
f[i][j]表示前i种糖果，至少有j个人的是不合法的方案数。
f[i][j]=f[i-1][j-k]*c[a[i]][k]*(a[i]*(a[i]-1)*(a[i]-2)**[乘k次]）
最后把其他的全排列f[n][i]=f[n][i]*(n-i)!
然后容斥，if(i&1) ans-=f[n][i] else ans+=f[n][i];
然后ans/(a[i]!)
先把所有糖果都看成不一样的，最后除以每种糖果的数量的阶乘，就能保证本质不同了。
ORZ Claris。。
学会了不用全部开LL的方法了，在前面加一个1LL* 然后每次乘完就Mod
中间用到了线性求逆元，复习一下：ny[i]=(Mod-Mod/i)*ny[Mod%i]%Mod
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Mod 1000000009 8 #define Maxn 2010 9 #define LL long long 10 11 int a[Maxn],c[Maxn][Maxn],pw[Maxn],ny[Maxn]; 12 int f[Maxn][Maxn]; 13 14 int main() 15 { 16 int n; 17 scanf("%d",&n); 18 memset(a,0,sizeof(a)); 19 for(int i=1;i<=n;i++) 20 { 21 int x; 22 scanf("%d",&x); 23 a[x]++; 24 } 25 for(int i=0;i<=n;i++) c[i][0]=1; 26 for(int i=1;i<=n;i++) 27 for(int j=1;j<=i;j++) 28 { 29 c[i][j]=(c[i-1][j-1]+c[i-1][j])%Mod; 30 } 31 int ans=0; 32 pw[0]=1; 33 for(int i=1;i<=n;i++) pw[i]=1LL*pw[i-1]*i%Mod; 34 ny[0]=ny[1]=1; 35 for(int i=2;i<=n;i++) ny[i]=1LL*(Mod-Mod/i)*ny[Mod%i]%Mod; 36 for(int i=2;i<=n;i++) ny[i]=1LL*ny[i]*ny[i-1]%Mod; 37 memset(f,0,sizeof(f)); 38 f[0][0]=1; 39 for(int i=1;i<=n;i++) 40 for(int j=0;j<=n;j++) 41 for(int k=0;k<=a[i];k++) 42 { 43 if(k>j) break; 44 f[i][j]=(f[i][j]+1LL*f[i-1][j-k]*c[a[i]][k]%Mod*pw[a[i]]%Mod*ny[a[i]-k]%Mod)%Mod; 45 } 46 for(int i=0;i<=n;i++) 47 { 48 if(i&1) ans-=1LL*f[n][i]*pw[n-i]%Mod; 49 else ans+=1LL*f[n][i]*pw[n-i]%Mod; 50 ans=(ans%Mod+Mod)%Mod; 51 } 52 for(int i=1;i<=n;i++) if(a[i]) ans=(1LL*ans*ny[a[i]])%Mod; 53 printf("%d ",ans); 54 return 0; 55 }
2017-04-11 14:25:31