小w的喜糖(candy)
题目描述
废话不多说,反正小w要发喜糖啦!!
小w一共买了n块喜糖,发给了n个人,每个喜糖有一个种类。这时,小w突发奇想,如果这n个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。
两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。
输入
第一行,一个整数n。
接下来n行,每行一个整数,第i个整数Ai表示开始时第i个人手中的糖的种类。
输出
一行,一个整数Ans,表示方案数模1000000009。
样例输入
6
1
1
2
2
3
3
样例输出
10
提示
【数据规模和约定】
对于所有数据,1≤Ai≤k。
数据点 | n | k | 约束 |
1 | ≤10 | ≤10 | 无 |
2 | |||
3 | ≤20 | n | 每个人的糖果种类都不一样 |
4 | ≤100 | ||
5 | ≤2000 | ||
6 | |||
7 | ≤200 | 3 | 无 |
8 | |||
9 | |||
10 | |||
11 | ≤n | ||
12 | |||
13 | |||
14 | |||
15 | ≤2000 | ||
16 | |||
17 | |||
18 | |||
19 | |||
20 |
solution
背景(没用)
错排:求1~n的排列ai,满足ai!=i的个数
有重复元素的排列
好的,接下来才是正经的题解
令f[i][j]表示前i种糖,有j个人拿到了原来的糖的方案数
考虑算f[i][j]
也就是第i种糖,有k个人不合法
就这样啦
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 2005
#define mod 1000000009
using namespace std;
int n,cnt[maxn],t;
long long ans,ny[maxn],f[maxn][maxn],h[maxn];
long long work(long long k,long long num){
long long tmp=1;
while(num){
if(num&1)tmp=tmp*k;
k=k*k;k%=mod;tmp%=mod;num/=2;
}
return tmp;
}
long long C(int n,int m){
long long tmp=0;
tmp=(1LL*h[n]*ny[m]%mod)*ny[n-m];tmp%=mod;
return tmp;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&t);
cnt[t]++;
}
h[0]=1;ny[0]=1;
for(int i=1;i<=n;i++){
h[i]=(1LL*h[i-1]*i)%mod;
ny[i]=work(h[i],mod-2);
}
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++){
for(int k=0;k<=cnt[i];k++){
if (k>j)break;
f[i][j]+=(1LL*f[i-1][j-k]*C(cnt[i],k))%mod*ny[cnt[i]-k];
f[i][j]%=mod;
}
}
int op=1;
for(int i=0;i<=n;i++){
ans+=(1LL*f[n][i]*(h[n-i]*op))%mod;
op=op*(-1);
}
ans=(ans%mod+mod)%mod;
cout<<ans<<endl;
return 0;
}