bzoj_4665 小w的喜糖

题目:

  废话不多说,反正小w要发喜糖啦!!
  小w一共买了n块喜糖,发给了n个人,每个喜糖有一个种类。这时,小w突发奇想,如果这n个人相互交换手中的糖,那会有多少种方案使得每个人手中的糖的种类都与原来不同。
  两个方案不同当且仅当,存在一个人,他手中的糖的种类在两个方案中不一样。

思路:

  如果设第 种糖有 个,但是至少有 在原来那个人手中。那么这时的方案数就是 。然后再利用这个值容斥,得到 ,注意到整个表达式出来分母以外的部分都只与 有关,所以可以用 求出每个 对应的 ,最后再乘上剩下的式子即可。
  

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2005, MOD = 1000000009;

int fac[N], ifac[N];
int qkpow(int x, int k) {
    int ans = 1;
    for(; k; k >>= 1, x = (ll) x * x % MOD)
        if(k & 1) ans = (ll) ans * x % MOD;
    return ans;
}
int inv(int a) {
    return qkpow(a, MOD - 2);
}
void init(int n) {
    fac[0] = 1; 
    rep(i, 1, n) fac[i] = (ll) fac[i - 1] * i % MOD;
    ifac[n] = inv(fac[n]);
    drep(i, n - 1, 0) ifac[i] = (ll) ifac[i + 1] * (i + 1) % MOD;
}
int C(int x, int y) {
    return (ll) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}

int a[N], dp[N][N];
int main() {
    int n, x;
    scanf("%d", &n);
    init(n);
    rep(i, 1, n) {
        scanf("%d", &x);
        a[x]++;
    }
    int now = 0;
    dp[0][0] = 1;
    rep(i, 1, n) {
        rep(j, 0, now)
            rep(k, 0, a[i]) {
                int tmp = (ll) C(a[i], k) * ifac[a[i] - k] % MOD;
                (dp[i][j + k] += (ll) dp[i - 1][j] * tmp % MOD) %= MOD;
            }
        now += a[i];
    }
    int ans = 0;
    rep(i, 0, n) {
        int tmp = fac[n - i] * (i % 2 ? -1 : 1);
        (ans += (ll) dp[n][i] * tmp % MOD) %= MOD;
    }
    printf("%d\n", (ans + MOD) % MOD);
    return 0;
}