小w的喜糖
题目链接：https://lydsy.com/JudgeOnline/problem.php?id=4665
数据范围：略。
题解：
二项式反演裸题。
$f_{i,j}$表示，前$i$种钦定$j$拿到自己种类糖果的方案数。
求完了之后可以二项式反演回来即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000009 ;
int n, m;
ll ans;
int col[2010], s[2010], v[2010];
ll c[2010][2010], f[2010][2010], jc[2010], ine[2010], jcc[2010];
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
int main() {
n = rd();
for (int i = 0; i <= n; i ++ ) {
c[i][0] = 1;
for(int j = 1; j <= i; j ++ ) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
jc[0] = ine[0] = jcc[0] = jc[1] = ine[1] = jcc[1] = 1;
for (int i = 2; i <= n; i ++ ) {
jc[i] = (ll)jc[i - 1] * i % mod;
ine[i] = mod - (mod / i) * ine[mod % i] % mod;
jcc[i] = (ll)jcc[i - 1] * ine[i] % mod;
}
for (int i = 1; i <= n; i ++ ) {
col[i] = rd();
}
sort(col + 1, col + n + 1);
for (int i = 1; i <= n; i ++ ) {
if (col[i] > col[i - 1]) {
m ++ ;
}
v[m] ++ ;
}
for(int i = 1; i <= m; i ++ ) {
s[i] = s[i - 1] + v[i];
}
f[0][0] = 1;
for (int i = 1; i <= m; i ++ ) {
for (int j = 0; j <= s[i - 1]; j ++ ) {
for (int k = 0; k <= v[i]; k ++ ) {
f[i][j + k] = (f[i][j + k] + (ll)f[i-1][j] * c[v[i]][k] % mod * jc[v[i]] % mod * jcc[v[i] - k] % mod) % mod;
}
}
}
for (int i = 0; i <= n; i ++ ) {
ans = (ans + (ll)((i & 1) ? -1 : 1) * f[m][i] * jc[n - i] + mod) % mod;
}
for (int i = 1; i <= m; i ++ ) {
ans = (ll)ans * jcc[v[i]] % mod;
}
cout << ans << endl ;
return 0;
}