P5824十二重计数法，如何为？
摘要：P5824 十二重计数法 大意 有 (n) 个球和 (m) 个盒子，球要全部装进盒子里。 (text{I})：球之间互不相同，盒子之间互不相同。 (text{II})：球之间互不相同，盒子之间互不相同，每个盒子至多装一个
P5824 十二重计数法
大意
有 \(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}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。
思路
\(\text{I}\)：球之间互不相同，盒子之间互不相同。
显然答案是 \(m ^ n\)。
\(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
每次选择一个没装过球的盒子，答案就是 \(m ^ {\underline{n}}\)。
\(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。
第一种方式理解：
我们先考虑把 \(n\) 个不同的球，放在 \(m\) 个相同的盒子里，且盒子不为空，那么这样的答案就是第二类斯特林数，答案为 \(n \brace m\)，可是这个题的盒子是不相同的，我们将盒子编上号，再乘上 \(m!\) 的贡献，答案就是 \(m! {n \brace m}\)。
第二种方式理解：
我们采用容斥原理，全集即为 \(n\) 个不同的球随意的放入 \(m\) 个不同的盒子里，答案就是 \(m ^ n\)，但是我们要求盒子不为空，我们知道至少 \(k\) 个盒子为空的方案数即为 \(\binom{m}{k} (m - k) ^ n\)，容斥一下，故最终答案就是 \(\sum_{k = 0} ^ {m} (-1) ^ k \binom{m}{k} (m - k) ^ n\)。
\(\text{IV}\)：球之间互不相同，盒子全部相同。
我们可以先看 \(\text{VI}\)。
看完 \(\text{VI}\) 之后，我们发现区别就是这个盒子可以为空，我们只需要枚举几个盒子里面装了球，则答案是 \(\sum_{i = 1} ^ m {n \brace i}\)，就是同一行的和，直接用卷积算出来第 \(m\) 行的系数，答案就是将这一行加起来。
\(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
盒子全部相同，放哪都行，答案本质上都是一样的，即为 \([n \le m]\)。注：\([]\) 表示艾弗森括号。
\(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。
这个就是经典的第二类斯特林数，表示的就是 \(n\) 个不同的球放到 \(m\) 个相同的盒子里，盒子必须非空的方案数，就是 \(n \brace m\)，对于第二类斯特林数，我们可以采用递推的求法，\({n \brace m} = {n - 1 \brace m - 1} + m {n - 1 \brace m}\)，这个是什么意思呢？首先 \({n - 1 \brace m - 1}\) 的意思是开个新盒子，\(m {n - 1 \brace m}\) 就是用旧的盒子。
对于 \(\mathcal{O}(nm)\) 的做法，我们可以考虑直接递推，但是如果是 \(\mathcal{O}(n \log n)\) 就需要更厉害的做法了。
我们考虑 \(n \brace m\) 的通项公式 \({n \brace m} = \sum_{i = 0}^m \frac{(-1) ^ {m - i} i ^ n}{i!(m - i)!}\)，我们可以直接将这个式子写为卷积的形式，我们按 \(i\) 与 \(m - i\) 进行分隔：
\[\left\{ \begin{matrix} n \\ m \end{matrix} \right\} = \sum_{i = 0}^m \left( \frac{(-1)^{m-i}}{(m-i)!} \right) \cdot \left( \frac{i^n}{i!} \right)
\]
这显然符合 \((f * g)_m\) 的形式，即为 \(\sum_{i = 0} ^ m f(m - i)g(i)\)，定义两个多项式（序列） \(A_k = \frac{(-1)^k}{k!}, B_k = \frac{k^n}{k!}\)，则 \({n \brace m} = (A * B)_m\)。
\(\text{VII}\)：球全部相同，盒子之间互不相同。
可以先看 \(\text{IX}\)。
和其最大的区别在于这个题目的盒子可以空，发挥人类智慧，我们扔进去 \(m\) 个虚拟球，这样再做插板法，你会发现十分有道理，答案即为 \(\binom{n + m - 1}{m - 1}\)。
\(\text{VIII}\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
显然答案是 \(\binom{m}{n}\)。
\(\text{IX}\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。
我们考虑，先在每一个盒子里面放一个球，或者说我们利用插板法，先把 \(n\) 个球排成一列，一共 \(n - 1\) 个空隙，我们要插入 \(m - 1\) 个板，那么答案显然是 \(\binom{n - 1}{m - 1}\)。
\(\text{X}\)：球全部相同，盒子全部相同。
经典的划分数问题，定义 \(p_{n, m}\) 为 \(n\) 个数，划分为若干个集合，每个最大的集合不超过 \(m\)，使得和为 \(n\)。
我们有递推式 \(p_{n, m} = p_{n - m, m} + p_{n - 1, m - 1}\)，如何理解呢？第一部分 \(p_{n - m, m}\) 表示：我们先把 \(n\) 对于每一个 \(m\) 都分 \(1\) 个，再把剩下的划分为 \(m\) 个集合。对于第二部分 \(p_{n - 1, m - 1}\) 表示，为我们先拿出来一个 \(1\)，再把剩下的 \(n - 1\) 划分为 \(m - 1\) 个集合。
这个显然是可以 \(\mathcal{O}(nm)\) 预处理，我们如果考虑更快的 \(\log\) 方法，就需要开始小巧思了。
我们考虑开始拆贡献，对于 \(n\) 来说，数字 \(1\) 可以出现 \(0,1,2,3 \cdots\) 次，我们对于 \(1\) 来说，每次贡献都是 \(1\)，所有选择可以用一个无穷级数表示 \(G_1(x) = (x ^ 0 + x ^ 1 + x ^ 2 + \cdots) = \sum_{k = 0}^{\infty} x ^ k\)，同样的，对于 \(i\) 来说 \(G_i(x) = (x ^ 0 + x ^ {i} + x ^ {2i} + \cdots) = \sum_{i = 0} ^ {\infty} x ^ {ki}\)，故总方案的生成函数 \(P(x)\) 就是将这些 \(G\) 乘起来：
\[P(x) = G_1(x) \cdot G_2(x) \cdots = \prod_{i = 1}^{\infty} G_i(x)
\]
带入等比级数求和公式 \(\sum_k^{\infty} x ^ {ki} = \frac{1}{1 - x ^ i}\)，我们得到最终的公式：
\[P(x) = \prod_{i = 1} ^ {\infty} \frac{1}{1 - x ^ i}
\]
接下来有两种方法，第一种不太推荐，是求 \(\mathtt{Exp}\) 的方法，比较吃基础，第二种只需要会多项式求逆即可。
方法一：求 \(\mathtt{Exp}\)
我们先对于 \(P(x)\) 取自然对数：
\[\ln P(x) = \ln \left(\prod_{i = 1} ^ {\infty} \frac{1}{1 - x ^ i}\right) = \sum_{i = 1} ^ {\infty} \ln\left(\frac{1}{1 - x ^ i}\right)
\]
利用对数展开式 \(-\ln(1 - t) = \sum_{j = 1}^{\infty} \frac{t ^ j}{j}\)，我们只需要令 \(t = x ^ i\)，可以得到：
\[\ln P(x) = \sum_{i = 1} ^ {\infty} \sum_{j = 1} ^ {\infty} \frac{x ^ {ij}}{j}
\]
接着，我们需要继续化简，可是你可能没用头绪，我们化用牛老爷子的方法，即把前几项的系数写出来：
当 \(i=1\) 时（来自因子 \(\frac{1}{1-x^1}\)）：\(\frac{x^1}{1} + \frac{x^2}{2} + \frac{x^3}{3} + \frac{x^4}{4} + \dots\)
当 \(i=2\) 时（来自因子 \(\frac{1}{1-x^2}\)）：\(\frac{x^2}{1} + \frac{x^4}{2} + \frac{x^6}{3} + \dots\)
当 \(i=3\) 时（来自因子 \(\frac{1}{1-x^3}\)）：\(\frac{x^3}{1} + \frac{x^6}{2} + \frac{x^9}{3} + \dots\)
我们会发现，凡是满足 \(i \cdot j = k\) 的对 \((i, j)\)，都会贡献一个系数 \(\frac{1}{j}\) 给 \(x ^ {k}\)。
那么，我们直接换元，令 \(ij = k\)，然后再改变枚举顺序，先枚举 \(k\)：
\[\ln P(x) = \sum_{i = 1} ^ {\infty} \sum_{j = 1} ^ {\infty} \frac{x ^ {ij}}{j} \Longrightarrow \sum_{k = 1} ^ {\infty}\left( \sum_{i,j \wedge ij = k}\frac{1}{j} \right)x^k
\]
\(ij = k\) 保证了 \(j\) 必须是 \(k\) 的一个正因子，则括号内部分可以写为：
\[\sum_{j | k} \frac{1}{j}
\]
这个式子，如果莫反做的多了就会立刻想到用 \(d = \frac{k}{j}\)，我们发现，遍历 \(j\) 的过程，其实是和 \(d\) 对称的，约数嘛毕竟，故可以得出：
\[\sum_{j|k} \frac{1}{j} = \sum_{d|k} \frac{d}{k} = \frac{1}{k} \sum_{d|k} d
\]
我们发现后面的 \(\sum_{d | k} d\) 就是经典的数论函数 \(\sigma_1(k)\)，故 \(\ln P(x)\) 的第 \(k\) 项系数就是 \(\dfrac{\sigma_1(k)}{k}\)。
故最终答案就是 \(P(x) = \exp(A(x))\)。
方法二：五边形数
我们看我们刚刚推出来的划分数的生成函数：
\[P(x) = \prod_{i = 1} ^ {\infty} \frac{1}{1 - x ^ i}
\]
如果对其求倒数，则可以得到一个大名鼎鼎的欧拉函数：
\[\Phi(x) = \prod_{i = 1} ^ {\infty} (1 - x ^ i)
\]
而欧拉老爷子也对此颇有研究，展开后是一个极其稀疏多项式：
\[\Phi(x) = \sum_{k = -\infty} ^ {\infty} (-1) ^ k x ^ {\frac{k(3k - 1)}{2}}
\]
我们对于这个式子分解，区分 \(k < 0, k = 0, k > 0\) 的不同情况：
\[\Phi(x) = 1 + \sum_{i = 1}^{\infty}(-1) ^ k \left(x^\frac{k(3k - 1)}{2} + x ^ \frac{k(3k + 1)}{2} \right)
\]
因为 \(P(x) \cdot \Phi(x) = 1\)，所以答案就是 \(\text{PolyInv}(\Phi(x))\)。
\(\text{XI}\)：球全部相同，盒子全部相同，每个盒子至多装一个球。
盒子全部相同，球也相同，放哪都行，答案本质上都是一样的，即为 \([n \le m]\)。注：\([]\) 表示艾弗森括号。
\(\text{XII}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。
我们考虑先每个盒子放一个，再放剩下的，随便放，依旧划分数，答案为 \(p_{n - m, m}\)。
代码
#include<iostream>
using namespace std;
#define ll long long
const int MOD = 998244353;
const int MAXN = 1e6 + 5;
const int G = 3;
const int Gi = 332748118;
ll n, m;
ll fact[MAXN], inv[MAXN];
int rev[MAXN << 2];
ll S2[MAXN], Polya[MAXN << 2], Polyb[MAXN << 2];
ll tmp_inv[MAXN << 2], ln_tmp1[MAXN << 2], ln_tmp2[MAXN << 2];
ll exp_tmp[MAXN << 2], PolyG[MAXN << 2], PolyF[MAXN << 2];
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
ll C(ll n, ll m){
if(m < 0 || m > n) return 0;
return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
}
void NTT(ll A[], int len, int op){
for(int i = 0;i < len;i ++) if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1;mid < len;mid <<= 1){
ll Wn = qpow(op == 1 ? G : Gi, (MOD - 1) / (mid << 1));
for(int i = 0;i < len;i += (mid << 1)){
ll wk = 1;
for(int j = 0;j < mid;j ++, wk = wk * Wn % MOD){
ll x = A[i + j], y = wk * A[i + j + mid] % MOD;
A[i + j] = (x + y) % MOD;
A[i + j + mid] = (x - y + MOD) % MOD;
}
}
}
if(op == -1){
ll invL = qpow(len, MOD - 2);
for(int i = 0;i < len;i ++) A[i] = A[i] * invL % MOD;
}
}
void NTT_init(int len){
int L = 0; while((1 << L) < len) L ++;
for(int i = 0;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void init(){
fact[0] = 1;
for(int i = 1;i < MAXN;i ++){
fact[i] = fact[i - 1] * i % MOD;
}
inv[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);
for(int i = MAXN - 2;i >= 0;i --){
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
int len = 1;
while(len <= 2 * m) len <<= 1;
NTT_init(len);
for(int i = 0;i < len;i ++) Polya[i] = Polyb[i] = 0;
ll flag = 1;
for(int i = 0;i <= m;i ++){
Polya[i] = inv[i] * flag % MOD;
Polyb[i] = qpow(i, n) * inv[i] % MOD;
flag = (MOD - flag);
}
NTT(Polya, len, 1);
NTT(Polyb, len, 1);
for(int i = 0;i < len;i ++){
Polya[i] = Polya[i] * Polyb[i] % MOD;
}
NTT(Polya, len, -1);
for(int i = 0;i <= m;i ++){
S2[i] = Polya[i];
}
// cout << S2[m] << '\n';
}
void PolyInv(ll A[], ll B[], int N){
if(N == 1){
B[0] = qpow(A[0], MOD - 2);
return;
}
PolyInv(A, B, (N + 1) >> 1);
int len = 1;
while(len < (N << 1)) len <<= 1;
NTT_init(len);
for(int i = 0;i < N;i ++) tmp_inv[i] = A[i];
for(int i = N;i < len;i ++) tmp_inv[i] = 0;
NTT(tmp_inv, len, 1);
NTT(B, len, 1);
for(int i = 0;i < len;i ++){
B[i] = B[i] * (2 - tmp_inv[i] * B[i] % MOD + MOD) % MOD;
}
NTT(B, len, -1);
for(int i = N;i < len;i ++) B[i] = 0;
}
void PolyLn(ll A[], ll B[], int N){
int len = 1;
while(len < (N << 1)) len <<= 1;
for(int i = 0;i < len;i ++) ln_tmp1[i] = ln_tmp2[i] = 0;
PolyInv(A, ln_tmp1, N);
for(int i = 1;i < N;i ++) ln_tmp2[i - 1] = A[i] * i % MOD;
NTT_init(len);
NTT(ln_tmp1, len, 1);
NTT(ln_tmp2, len, 1);
for(int i = 0;i < len;i ++) ln_tmp1[i] = ln_tmp1[i] * ln_tmp2[i] % MOD;
NTT(ln_tmp1, len, -1);
B[0] = 0;
for(int i = 1;i < N;i ++) B[i] = ln_tmp1[i - 1] * qpow(i, MOD - 2) % MOD;
for(int i = N;i < len;i ++) B[i] = 0;
}
void PolyExp(ll A[], ll B[], int N){
if(N == 1){
B[0] = 1;
return;
}
PolyExp(A, B, (N + 1) >> 1);
for(int i = 0;i < (N << 1);i ++) exp_tmp[i] = 0;
PolyLn(B, exp_tmp, N);
int len = 1;
while(len < (N << 1)) len <<= 1;
NTT_init(len);
for(int i = 0;i < N;i ++) exp_tmp[i] = (A[i] - exp_tmp[i] + MOD) % MOD;
exp_tmp[0] = (exp_tmp[0] + 1) % MOD;
for(int i = N;i < len;i ++) exp_tmp[i] = 0;
NTT(B, len, 1);
NTT(exp_tmp, len, 1);
for(int i = 0;i < len;i ++) B[i] = B[i] * exp_tmp[i] % MOD;
NTT(B, len, -1);
for(int i = N;i < len;i ++) B[i] = 0;
}
void EXP_init(){
for(int i = 1;i <= m;i ++){
for(int j = 1;i * j <= n;j ++){
PolyG[i * j] = (PolyG[i * j] + qpow(j, MOD - 2)) % MOD;
}
}
PolyExp(PolyG, PolyF, n + 1);
}
void solve1(){
cout << qpow(m, n) << '\n';
}
void solve2(){
if(n > m) cout << 0 << '\n';
else cout << C(m, n) * fact[n] % MOD << '\n';
}
void solve3(){
ll ans = 0;
ll flag = 1;
for(int i = 0;i <= m;i ++){
ll cnt = flag * C(m, i) % MOD;
cnt = cnt * qpow(m - i, n) % MOD;
ans = (ans + cnt + MOD) % MOD;
flag = (MOD - flag);
}
cout << ans << '\n';
}
void solve4(){
ll ans = 0;
for(int i = 1;i <= m;i ++){
ans = (ans + S2[i]) % MOD;
}
cout << ans << '\n';
}
void solve5(){
cout << (n <= m) << '\n';
}
void solve6(){
cout << S2[m] << '\n';
}
void solve7(){
cout << C(n + m - 1, m - 1) << '\n';
}
void solve8(){
cout << C(m, n) << '\n';
}
void solve9(){
cout << C(n - 1, m - 1) << '\n';
}
void solve10(){
cout << PolyF[n] << '\n';
}
void solve11(){
cout << (n <= m) << '\n';
}
void solve12(){
if(n <= m) cout << 0 << '\n';
else cout << PolyF[n - m] << '\n';
}
int main(){
cin >> n >> m;
init();
EXP_init();
solve1();
solve2();
solve3();
solve4();
solve5();
solve6();
solve7();
solve8();
solve9();
solve10();
solve11();
solve12();
return 0;
}