题解 [牛客练习赛64 D] 宝石装箱

• 宝石装箱

题目描述

有 个带标号盒子和球，每个球都有一个盒子 不能放进去（ 不一定是排列）。

问每一个盒子里都有一个球的方案数。

正解

每一个球都有一个限制（一个盒子不能放）。

这个问题类似于错排，而错排有一种容斥的解法。

设 表示至少有 条限制不满足的方案数, 表示恰好有 条限制不满足的方案数。（一种方案必须放满所有盒子）

先钦定 个盒子一定不合法，然后其他盒子随便摆，这就是至少 个盒子不合法的方案数 。

那么有 ：

特别的，。

现在问题变成了如何求 。

可能有多个 相同，但是只能有一个球放进这个 这个盒子，设 为有多少个球不能放进第 个盒子里。

对于每一个 分开考虑，于是每一个 可以看成系数为 的物品，跑一遍背包就能求出 "先钦定 个位置不合法" 的方案数。

这还没完，钦定完一些位置不合法，还要考虑上其他位置，需要乘上一个阶乘才是至少有 个位置不合法的方案数。

最后答案？显然就是 呀。

总结

为什么要容斥

因为 "至少" 比 "恰好" 限制更少，更好求，于是要容斥。

"至少" 与 "恰好" 的关系怎么推得，为什么是这个关系

这个组合数不是很显然吗？

这个我只能说熟能生巧，做多了可能就记住了这个容斥系数了。

代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
const int N = 8005;

int n;
int a[N], b[N];
int f[N], fac[N], ifac[N];

inline int fpm(int x, int y) {
    int r = 1;
    while(y) {
        if(y & 1) r = 1LL * r * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return r;
}

inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; }
inline int comb(int x, int y) { return 1LL * perm(x, y) * ifac[y] % mod; }

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++b[a[i]];
    }

    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1LL * i * fac[i - 1] % mod;
    ifac[n] = fpm(fac[n], mod - 2);
    for(int i = n; i; --i) ifac[i - 1] = 1LL * i * ifac[i] % mod;

    f[0] = 1;
    for(int i = 1; i <= n; ++i) {
        if(!b[i]) continue;
        for(int j = n; j >= 1; --j)
            f[j] = (f[j] + 1LL * b[i] * f[j - 1]) % mod;
    }

    for(int i = 0; i <= n; ++i)
        f[i] = 1LL * f[i] * fac[n - i] % mod;
    for(int i = n; i >= 0; --i)
        for(int j = i - 1; j >= 0; --j)
            f[j] = (f[j] - 1LL * comb(i, j) * f[i] % mod + mod) % mod;
    printf("%d\n", f[0]);
    return 0;
}