解法

这道题是 DP + 容斥，正好是我不怎么会的类型。设状态\(f[i][j]\)为「考虑了前\(i\)个状态之后有\(j\)个颜色与原来一样的方案数（注意这里颜色不一样不是本质不同的）」。可以推出式子：

\[ dp[i][j] = \sum_{k = 0}^j dp[i – 1][j – k] {cnt[i] \choose k} \frac{cnt[i]!}{(cnt[i] – k)!} \]

其中我们枚举\(k\)为本次考虑时，与本身颜色一样的喜糖个数，从上一个状态转移之后乘上组合数（选法），然后再乘上选喜糖的方案数（目前我们把所有糖果看成本质不同的东西）。

最终的答案容斥一下：

\[ ans = dp[n][0]*(n-0)! – dp[n][1]*(n-1)! + dp[n][2]*(n-2)! \dots \]

其中阶乘代表的是剩下的人随意选择糖果的方案数。

代码

// BZ4665.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_N = 2020, mod = 1000000009;
ll n, arr[MAX_N], level[MAX_N], level_rev[MAX_N], dp[MAX_N][MAX_N], cnt[MAX_N];

ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

ll comb(ll a, ll b)
{
    return level[a] * level_rev[a - b] % mod * level_rev[b] % mod;
}

int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), cnt[arr[i]]++;

    level[0] = level[1] = level_rev[0] = level_rev[1] = 1;
    for (ll i = 2; i < MAX_N; i++)
        level[i] = level[i - 1] * i % mod;
    level_rev[MAX_N - 1] = quick_pow(level[MAX_N - 1], mod - 2);
    for (ll i = MAX_N - 1; i >= 3; i--)
        level_rev[i - 1] = level_rev[i] * i % mod;
    dp[0][0] = 1;
    for (ll i = 1; i <= n; i++)
        for (ll j = 0; j <= n; j++)
            for (ll k = 0; k <= cnt[i]; k++)
            {
                if (k > j)
                    break;
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * comb(cnt[i], k) % mod * level[cnt[i]] % mod * level_rev[cnt[i] - k] % mod) % mod;
            }
    ll ans = 0;
    for (ll i = 0; i <= n; i++)
    {
        dp[n][i] = (dp[n][i] * level[n - i] % mod);
        if (i & 1)
            dp[n][i] = (dp[n][i] * (-1) + mod) % mod;
        ans = (ans + dp[n][i] + mod) % mod;
    }
    for (ll i = 1; i <= n; i++)
        ans = ans * level_rev[cnt[i]] % mod;
    printf("%lld", ans);
    return 0;
}