小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;

}