BZOJ4665 小w的喜糖

题解
动态规划, 容斥

Description

$n$ 颗糖发给了 $n$ 个人，每颗糖有一个种类。$n$ 个人相互交换手中的糖那么有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

答案对 $10^9 + 9$ 取模

答案对 $10^9 + 9$ 取模！！！！！ $10^9 + 9$ ！！！！ $10^9 + 9$ ！！！！！ $10^9 + 9$ ！！！！！

Solution

可以暂时不考虑相同种类糖之间的关系，把它们当成不同的最后把答案乘上 $\frac{1}{\Pi_{i} a_i!}$ . $a_i$ 表示种类 $i$ 的糖数

设 $dp[i][j]$ 表示前 $i$ 种糖至少有 $j$ 个人不合法（即手中拿的糖和原来一样。那么有

然后对于答案就可以直接容斥得到

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Author: AcFunction
 * Date:   2019-03-04 21:07:09
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

const int N = 2005; 
const ll mod = (ll)1e9 + 9; 

ll fpw(ll x, ll k, ll p) {
  ll ret = 1; 
  while(k) {
    if(k & 1) ret = ret * x % p; 
    x = x * x % p; k >>= 1; 
  } return ret; 
}

int n, a[N]; 
ll dp[N][N], inv[N], invf[N], fac[N]; 

void prework() {
  inv[1] = fac[0] = fac[1] = invf[0] = invf[1] = 1; 
  rep(i, 2, n) 
    inv[i] = (mod - mod / i) * inv[mod % i] % mod, 
    fac[i] = fac[i - 1] * i % mod, 
    invf[i] = invf[i - 1] * inv[i] % mod; 
}

ll C(int n, int m) {
  if(n < m) return 0; 
  return fac[n] * invf[m] % mod * invf[n - m] % mod; 
}

int main() {
  INIT(); 
  cin >> n; 
  prework(); 
  rep(i, 1, n) { int t; cin >> t; a[t]++; } 
  ll ans = 0; dp[0][0] = 1; 
  rep(i, 1, n) rep(j, 0, n)
    rep(k, 0, min(a[i], j)) 
      dp[i][j] += 1ll * dp[i - 1][j - k] * C(a[i], k) % mod * fac[a[i]] % mod * invf[a[i] - k] % mod, 
      dp[i][j] %= mod; 
  // rep(i, 0, n) cout << dp[n][i] << " "; 
  rep(i, 0, n) ans += 1ll * ((i & 1) ? -1 : 1) * dp[n][i] % mod * fac[n - i] % mod, ans %= mod, ans += mod, ans %= mod; 
  rep(i, 1, n) ans *= invf[a[i]], ans %= mod; 
  cout << ((ans % mod + mod) % mod);  
  return 0; 
}