十二重计数法

组合数学是一门古老而迷人的学科。

传说早在 \(114514\) 年前，一位名为忆哀的神灵来到地球，发现了人类——另一种有智慧的物种。

她觉得这很有趣，为了加速人类文明的发展，她向人间传下了一类计数问题——十二重计数，这也正是组合数学的开端。

而只有搞明白这类问题，才能在组合数学上继续深入。

有 \(n\) 个球和 \(m\) 个盒子，要全部装进盒子里。

还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）

限制条件分别如下：

\(\text{I}\)：球之间互不相同，盒子之间互不相同。
\(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
\(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

\(\text{IV}\)：球之间互不相同，盒子全部相同。
\(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
\(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

\(\text{VII}\)：球全部相同，盒子之间互不相同。
\(\text{VIII}\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
\(\text{IX}\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

\(\text{X}\)：球全部相同，盒子全部相同。
\(\text{XI}\)：球全部相同，盒子全部相同，每个盒子至多装一个球。
\(\text{XII}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。

orz \(\mathsf E \color{red}\mathsf{ntropyIncreaser}\)

碎碎念

一个非常重要的事情是我认为我完全不懂组合数学。

但是我又很喜欢组合数学的这种感觉，实在是太有魅力了。

接下来这些东西大概会长的比较像一个小学生写的笔记，见谅了，我基础一直不是很好。

其实把相同看作无标号，互不相同看作有标号就会好理解很多。

举一个例子，现在有三个球，没有标号，但是有两个有标号的盒子。

记 \((x, y)\) 表示在 \(x\) 号盒子里放了 \(y\) 个球（因为球没有标号，所以只关心数量）

那么 \(\{(1, 1), (2, 2)\}\) 和 \(\{(1, 2), (2, 1)\}\) 是两种不同的方案。

如果说球有标号的话，那么 \(\{(1, \{1\}), (2, \{2, 3\})\}\) 和 \(\{(1, \{2\}), (2, \{1, 3\})\}\) 就是两种不同的方案。

此时后面表示的是这个盒子里放了哪些球。

如果盒子没有标号，球有标号的话，那么 \(\{\{1, 2\}, \{3\}\}\) 和 \(\{\{3\}, \{1, 2\}\}\) 就没有区别。

笼统一点来说，盒子相同就是，不管盒子怎么排列，方案都是一个，这个时候可以只考虑其中一种排列。

球相同的话，我们就只关心球的数量，并不关心哪个球具体被分到哪个盒子里面了，只要保证分了 \(n\) 个球下去就行，这个可以类比 \(k\) 元一次不定方程（当然不定方程解的数目相当于球无标号且盒子有标号）。

题解

I.

没有限制的话，我们考虑盒子是困难的，因为你并不知道一个盒子最后会放多少个球进来。

如果反过来考虑球，因为球是互不相同的，我们只需要考虑球放到了哪个盒子就行。

于是 \(\text{I}\) 的方案数就是 \(m^n\)，因为每个球往任意一个盒子里放都是可行的。

II.

至多装一个球，相当于一个盒子放了之后就不能放了。

我们先任意放第一个球，这有 \(m\) 种选择，可以发现不管第一个球放在哪里，第二个球都有 \(m - 1\) 种方法。

于是根据乘法原理，有 \(m(m - 1)\) 种方案。

进而我们可以发现答案就是 \(m^{\underline{n}}\)。

III.

可以考虑类似插板法那样的东西？

先钦定每个盒子必须有一个，因为盒子本身是有标号的所以 \(\dbinom{n}{m}m!\) 种方案。

剩下的就是 \(n - m\) 个有标号球，\(m\) 个有标号盒子，无限制随便放，就是 I，于是答案是 \(\dbinom{n}{m}m!m^{n - m}\)。

但是一个问题是，这个东西不对！为什么呢？它算重了！准确来说我们这里在尝试钦定每个盒子的第一个球，但实际上我们并不能做到钦定这个球，因为按照这种算法，如果有一个盒子，被钦定的球是 \(1\)，后面放进来两个球 \(2,3\)，和这个盒子被钦定的球是 \(2\)，后面放进来两个球 \(1, 3\) 会被分开计算，但实际上它们是同一个方案。

所以这并不构成一个双射，自然也不能以这样的方式计数。

如果要说的更具体化一点，因为球有标号，所以我们每个盒子里面可以被钦定的球可能有多个。

那么你为了保证不算重，我们需要考虑把一个盒子里的所有情况归为一种，这就需要我们知道盒子里有多少个球。

而我们此时是在计数，并不关心每个盒子里具体有多少，我们只关心有多少方案合法。

换句话说如果想要按照这种方式做下去，我们需要额外枚举每个盒子分别放了多少个，这样来做的话和暴力统计也差不了多少了。

再深入一点，我们这里的钦定是在钦定“合法”，这样是不好做的，于是我们反过来，钦定“不合法”。

要想清楚，“钦定”的意思是，强制让某些元素一定满足一个限制，其他的认为没有限制，最后通过类似容斥的方法算出并集。

此处的限制是“至少一个=没有空盒”，于是我们钦定某一些一定是空盒，然后剩下的转化为 I.，再做一个容斥就好了。

那么枚举有多少个是空盒，写出式子：

\[ ans_{\text{III}}(n, m) = \sum\limits_{i = 0}^{m}(-1)^i\dbinom{m}{i}(m - i)^n \]

VI.

这个和 III. 几乎是一样的，只是盒子可不可以排列的区别。

于是 \(ans_{\text{VI}}(n, m) = \dfrac{ans_{\text{III}}}{m!}\)。

另外，这就是第二类斯特林数 \(s2(n, m) = \begin{Bmatrix}n \\ m\end{Bmatrix}\)。

它存在另外一个做法，我们考虑递推，考虑新加入的这个元素是放入一个新集合，还是放入原有集合就可以。

那么递推式：\(\begin{Bmatrix}n \\ m\end{Bmatrix} = \begin{Bmatrix}n - 1 \\ m - 1\end{Bmatrix} + m\begin{Bmatrix}n - 1 \\ m\end{Bmatrix}\)。

IV.

是 VI. 的变种。

我们考虑枚举多少个盒子没空着就行了，于是问题转化为第二类斯特林数。

\[ ans_{\text{IV}}=\sum\limits_{i = 1}^m\begin{Bmatrix}n\\ i\end{Bmatrix} \]

V.

怎么感觉这个比较 shaber 啊，注意到至多放一个，所以答案是 \([n \le m]\)。

IX.

注意到一个事情是，这实际上等价于不定方程的整数解的数目。

因为盒子是有标号的，这就好比是不同的变量 \(x_{i}\)。

所以我们套用插板法，在 \(n - 1\) 个空里插 \(m - 1\) 个板子，答案为 \(\dbinom{n - 1}{m - 1}\)。

VII.

仍旧是插板法，这次我们借 \(m\) 个元素过来先。

这里就和 III. 不一样了，因为小球是没有区别的，我们可以钦定“第一个”元素。

于是方案为 \(\dbinom{n + m - 1}{m - 1}\)。

VIII.

相当于就是选出 \(n\) 个装，\(m - n\) 个不装。

那么方案数就是 \(\dbinom{m}{n}\)

X.

和第二类斯特林有点像，但是这个东西叫做划分数/分拆数。

就是注意到盒子和小球都没有区分，不能类似插板法那样随便乱插。

因为盒子没区分，所以我们需要钦定这是某一个排列，我们不妨钦定它为单调不增的（单调不降也行但是你发现不太好算）。

于是可以做一个递推：\(p(n, m) = p(n - m, m) + p(n, m - 1)\)。

解释就是，给所有已有的集合都放一个小球，保持单调不增，或者新开一个集合，里面没有小球。

为什么新开集合里面不放呢？因为我们并不知道之前的集合放了多少个，我们为了保证性质需要这么干。

XI.

比较shaber，答案和 V. 一样都是 \([n \le m]\)。

XII.

这里小球没有标号，于是我们还是借 \(m\) 个过来先，答案是 \(p(n - m, m)\)。

代码

如你所见，其实这个题的某些部分需要 poly，但是我最近的重点不在这上面，没啥时间继续弄了！

于是贺了多项式板子，之后再来进一步做思考吧。

// author : black_trees
// I'm Watanuki Taiga's dog!

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e6 + 10;
const int mod = 998244353;

const int g = 3;
const int invg = 332748118;

bool vis[si];

int n, m, cnt;
int limit, p[45330], r[si];

i64 ans[si];
i64 F[si], G[si];
i64 a[si], b[si], c[si], d[si], e[si];
i64 pw[si], inv[si], fac[si], invf[si];

i64 qpow(i64 a, int b) {
    i64 ret = 1 % mod;
    for(; b; b >>= 1) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret % mod;
}

void magic(int k) {
    int l = 0;
    limit = 1;

    while(limit < 2 * k) {
        limit *= 2, l++;
    }

    for(int i = 1; i < limit; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
}

void ntt(i64 *f, int type) {
    for(int i = 0; i < limit; i++) {
        if(i < r[i]) {
            swap(f[i], f[r[i]]);
        }
    }

    for(int mid = 1; mid < limit; mid *= 2) {
        i64 wn = type == 1 ? qpow(g, (mod - 1) / (2 * mid)) : qpow(invg, (mod - 1) / (2 * mid));
        for(int j = 0, R = 2 * mid; j < limit; j += R) {
            i64 w = 1;
            for(int k = 0; k < mid; k++, w = w * wn % mod) {
                i64 x = f[j + k], y = w * f[j + k + mid] % mod;
                f[j + k] = (x + y) % mod;
                f[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }

    if(type == -1) {
        i64 invl = qpow(limit, mod - 2);
        for(int i = 0; i < limit; i++) {
            f[i] = f[i] * invl % mod;
        }
    }
}

void getInv(i64 *f, i64 *invf, int k) {
    if(k == 1) {
        invf[0] = qpow(f[0], mod - 2);
        return;
    }

    getInv(f, invf, (k + 1) / 2), magic(k);
    for(int i = 0; i < k; i++) {
        a[i] = f[i];
    }
    for(int i = k; i < limit; i++) {
        a[i] = 0;
    }

    ntt(a, 1), ntt(invf, 1);
    for(int i = 0; i < limit; i++) {
        invf[i] = (2 - invf[i] * a[i] % mod + mod) % mod * invf[i] % mod;
    }

    ntt(invf, -1);
    for(int i = k; i < limit; i++) {
        invf[i] = 0;
    }
}

void getDev(const i64 *f, i64 *devf, int k) {
    for(int i = 0; i < k - 1; i++) {
        devf[i] = f[i + 1] * (i + 1) % mod;
    }
    devf[k - 1] = 0;
}

void getCal(const i64 *f, i64 *calf, int k) {
    calf[0] = 0;
    for(int i = 1; i < k; i++) {
        calf[i] = f[i - 1] * inv[i] % mod;
    }
}

void getMul(i64 *f, i64 *g) {
    ntt(f, 1);
    ntt(g, 1);
    for(int i = 0; i < limit; i++) {
        f[i] = f[i] * g[i] % mod;
    }
    ntt(f, -1);
}

void getLn(i64 *f, i64 *lnf, int k) {
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));

    getInv(f, b, k), getDev(f, c, k);
    magic(k), getMul(b, c), getCal(b, lnf, k);
}

void getExp(i64 *f, i64 *expf, int k) {
    if(k == 1) {
        expf[0] = 1;
        return;
    }

    getExp(f, expf, (k + 1) / 2);
    magic(k), getLn(expf, d, k);
    for(int i = 0; i < k; i++) {
        e[i] = f[i];
    }
    for(int i = k; i < limit; i++) {
        e[i] = 0;
    }

    ntt(expf, 1), ntt(d, 1), ntt(e, 1);
    for(int i = 0; i < limit; i++) {
        expf[i] = (e[i] - d[i] + 1 + mod) % mod * expf[i] % mod;
    }

    ntt(expf, -1);
    for(int i = k; i < limit; i++) {
        expf[i] = 0;
    }
}

void init() {
    pw[1] = 1;
    inv[1] = fac[0] = fac[1] = 1;
    invf[0] = invf[1] = F[0] = 1;
    for(int i = 2; i <= n + m; i++) {
        if(!vis[i]) {
            p[cnt++] = i;
            pw[i] = qpow(i, n);
        }
        for(int j = 0; j < cnt && i * p[j] <= n + m; j++) {
            vis[i * p[j]] = true;
            pw[i * p[j]] = pw[i] * pw[p[j]] % mod;
            if(i % p[j] == 0) {
                break;
            }
        }
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
        fac[i] = fac[i - 1] * i % mod;
        invf[i] = invf[i - 1] * inv[i] % mod;
    }

    for(int i = 1; i <= m; i++) {
        F[i] = mod - F[i - 1] * inv[i] % mod;
        G[i] = pw[i] * invf[i] % mod;
    }

    magic(m + 1);
    ntt(F, 1), ntt(G, 1);
    for(int i = 0; i < limit; i++) {
        F[i] = F[i] * G[i] % mod;
    }

    ntt(F, -1);
}

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

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n >> m, init();

    ans[1] = pw[m];

    if(n > m) ans[2] = 0;
    else ans[2] = fac[m] * invf[m - n] % mod;

    if(n < m) ans[3] = 0;
    else ans[3] = fac[m] * F[m] % mod;

    for(int i = 1; i <= m; i++) {
        ans[4] = (ans[4] + F[i]) % mod;
    }

    if(n > m) ans[5] = 0;
    else ans[5] = 1;

    ans[6] = F[m];

    ans[7] = C(n + m - 1, m - 1);

    if(n > m) ans[8] = 0;
    else ans[8] = C(m, n);

    if(n < m) ans[9] = 0;
    else ans[9] = C(n - 1, m - 1);

    memset(F, 0, sizeof(F));
    memset(G, 0, sizeof(G));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m && i * j <= n; j++) {
            G[i * j] = (G[i * j] + inv[i]) % mod;
        }
    }
    getExp(G, F, n + 1), ans[10] = F[n];

    if(n > m) ans[11] = 0;
    else ans[11] = 1;

    if(n < m) ans[12] = 0;
    else ans[12] = F[n - m];

    for(int i = 1; i <= 12; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}

---

最后更新: September 14, 2023