\(\mathtt{Link}\)

P4640 [BJWC2008]王之财宝 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

\(\mathtt{Description}\)

\(m\) 个无区别球放进 \(n\) 个有区别盒子，可以有不放的球，可以有空盒，其中编号 \(1 \sim t\) 的盒子有容量限制 \(b_i\)，问放置方案数。对给定质数 \(p\) 取模。

\(\mathtt{Data} \text{ } \mathtt{Range} \text{ } \mathtt{\&} \text{ } \mathtt{Restrictions}\)

• \(1 \le m \le 10^9\)
• \(0 \le t \le n \le 10^9\)
• \(t \le 15\)
• \(1 < p \le 10^5\)
• \(0

\(\mathtt{Solution}\)

球盒问题，轻车熟路。

首先考虑简化问题到 \(m\) 个球都放进盒子中（不能不放），可以有空盒，没有容量限制。那么方案数是 \(\dbinom{n +m - 1}{m}\).（证明参见我写过的）

此时再考虑逐渐放宽问题一直到题目的样子，首先先将不能不放球的限制砍掉。

其实这个时候也就相当于没放的球自己独立进一个盒子，也就相当于盒子多了一个，\(m \leftarrow m + 1\)。结果为 \(\dbinom{n + m}{m} = \dbinom{n + m}{n}\).

现在再加入盒子容量的限制。观察到 \(t \le 15\)，考虑 \(2^t\) 状态压缩暴力枚举。

再考虑容斥原理，答案等于至少0个盒子超载方案数（上面刚刚求的）-至少任意1个盒子超载总方案数+至少任意2个盒子超载总方案数-至少任意3个盒子超载总方案数……

接下来举例说明：

总共有三个空间有限的盒子，至少 \(0\) 个盒子超载方案数：\(\dbinom{3 + m}{3}\)；

考虑至少让 \(1\) 个盒子超载：

• 将盒子 \(1\) 塞超，也就是塞满+1（容量+1），剩下的球在 \(3\) 个盒子里随便选着放，方案数：\(\dbinom{3+m-b_1-1}{3}\)；

• 将盒子 \(2\) 塞超，剩下的球在 \(3\) 个盒子里随便选着放，方案数：\(\dbinom{3+m-b_2-1}{3}\)；

• 将 \(3\) 塞超，…… \(\dbinom{3 + m - b_3 - 1}{3}\)。

第一个盒子的所有超载情况方案数就是上面三个结果的和，根据容斥的式子，总共需要减去这个和。

接下来，要至少让 \(2\) 个盒子超载：

首先把 \(1, 3\) 都塞超（每个盒子塞到它的容量+1），然后剩下的球在 \(3\) 个盒子里随便选着放的方案数：\(\dbinom{3+m-b_1-1-b_3-1}{3}\)；

然后把 \(2, 3\) 都塞超，剩下的球在 \(3\) 个盒子里随便选着放方案数：\(\dbinom{3+m-b_2-1-b_3-1}{3}\)；

最后把 \(1, 2\) 都塞超，方案数：\(\dbinom{3+m-b_1-1-b_2-1}{3}\)。

那么至少让 \(2\) 个盒子超载的方案数就是上面三个方案数的总和。根据容斥式子，总共需要加上这个和。

然后再让至少（总共就3个其实已经不是至少了） \(3\) 个盒子超载……：

就是所有都塞超：\(\dbinom{3 + m -b_1 - 1 - b_2 - 1 - b_3 - 1}{3}\)。

根据容斥的式子总共需要减去这个东西。

最后容斥统计，可以得到结果是这样一个东西：

\[\dbinom{3 + m}{3} - \dbinom{3+m-b_1-1}{3} - \dbinom{3+m-b_2-1}{3} -\dbinom{3 + m - b_3 - 1}{3} + \dbinom{3+m-b_1-1-b_3-1}{3} + \\ \quad\\ \dbinom{3+m-b_2-1-b_3-1}{3} + \dbinom{3+m-b_1-1-b_2-1}{3} - \dbinom{3 + m -b_1 - 1 - b_2 - 1 - b_3 - 1}{3} \]

到这里思路也就讲完了，但是还有一个东西：

考虑到上述这个式子就是很多的组合数相加相减，同时观察到这些组合数一一对应了所有 \(t\) 个盒子能构成的 \(2 ^ t\) 种选法。

实际上我们只需要暴力枚举 \(2^t\)，表示一种选法状态，计算出对应的组合数，然后根据选的数量的奇偶性决定它在总式子里做加数还是减数。

这部分的代码：

    for (int i = 0; i < (1 << t); ++i) {
        int cnt = 0, k = m;
        for (int j = 1; j <= t; ++j)
            if (i & (1 << j - 1)) {
                ++cnt;
                k -= b[j] + 1;
            }
        int g = lucas(n + k, n);
        (ans += (cnt & 1) ? p - g : g) %= p;
    }

对于组合数，考虑到 \(p\) 最大到 \(10^5\)，使用Lucas定理求解。

\(\mathtt{Time} \text{ } \mathtt{Complexity}\)

\(\operatorname{O}(p + 2^t \log (n + m))\)

\(\mathtt{Code}\)

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-05-04 10:55:29 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-05-04 11:12:58
 */
#include 
#include 

#define int long long

inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag) return x;
    return ~(x - 1);
}

const int maxp = 1e5 + 5;
const int maxt = 20;
int b[maxt];
int n, m, t, p;

inline int pow(int a, int b = p - 2LL) {
    int s = 1;
    for (; b; b >>= 1, (a *= a) %= p)
        if (b & 1)
            (s *= a) %= p;
    return s;
}

int fac[maxp], inv[maxp];

inline int C(int n, int m) {
    if (n < m)
        return 0;
    return fac[n] * inv[n - m] % p * inv[m] % p;
}

inline int lucas(int n, int m) {
    int ans = 1;
    for (; m; n /= p, m /= p)
        (ans *= C(n % p, m % p)) %= p;
    return ans;
}

signed main() {
    n = read();
    t = read();
    m = read();
    p = read();
    for (int i = 1; i <= t; ++i)
        b[i] = read();

    fac[0] = inv[0] = 1;
    for (int i = 1; i < p; ++i)
        fac[i] = fac[i - 1] * i % p;
    inv[p - 1] = pow(fac[p - 1]);
    for (int i = p - 2; i; --i)
        inv[i] = inv[i + 1] * (i + 1) % p;

    int ans = 0;
    for (int i = 0; i < (1 << t); ++i) {
        int cnt = 0, k = m;
        for (int j = 1; j <= t; ++j)
            if (i & (1 << j - 1)) {
                ++cnt;
                k -= b[j] + 1;
            }
        int g = lucas(n + k, n);
        (ans += (cnt & 1) ? p - g : g) %= p;
    }

    printf("%lld\n", ans);
    return 0;
}

推荐！