自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:14:41，当前版本为作者最后更新于2020-01-13 11:56:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$n$ 个球， $m$ 个盒子

一、球不同，盒子不同，无其他限制

显然为 $m^n$

二、球不同，盒子不同，每个盒子至多装一个球

考虑相当于每个球找一个没有被选过的盒子放进去。不难发现，方案数为 $m^{\underline{n}}$

三、球不同，盒子不同，每个盒子至少装一个球

考虑容斥：枚举多少个盒子空了，然后剩下的部分就是第一个部分了。然后就可以得到下面这个式子：

$$\sum_{i=0}^{m} (-1)^{i} \binom{m}{i} (m-i)^{n}$$

四、球不同，盒子相同，无其他限制

考虑第二类斯特林数： $S_{n,m}$ 表示 $n$ 个不同的元素组成 $m$ 个非空集合的方案数。

考虑枚举多少个盒子里头装了球，那么答案为：

$$\sum_{i=1}^{m} S_{n,i}$$

蒯 第二类斯特林数 · 行 就行了

五、球不同，盒子相同，每个盒子至多装一个球

最思博的部分了不论放到哪个盒子里头都是一样的，所以答案就是 $[n \leq m]$

六、球不同，盒子相同，每个盒子至少装一个球

根据第二类斯特林数的定义，显然答案为 $S_{n,m}$

七、球相同，盒子不相同，无其他限制

利用插板法，我们可以知道，答案为 $\binom{n+m-1}{m-1}$

八、球相同，盒子不相同，每个盒子至多装一个球

盒子不同，我们相当于要选出 $n$ 个盒子装球，剩下 $m-n$ 个盒子不装球。

所以答案就是 $\binom{m}{n}$

九、球相同，盒子不相同，每个盒子至少装一个球

同样利用插板法，我们先钦定每个盒子里头放一个球，剩下 $n-m$ 个球按照第七个做就行了。

答案即为 $\binom{n-1}{m-1}$

十、球相同，盒子相同，无其他限制

设 $p_{n,m}$ 表示“划分数”——即将 $n$ 划分成 $m$ 个自然数的可重集的方案数。那么我们要的答案就是 $p_{n,m}$

这个东西有一个非常经典的时空复杂度为 $O(n^2)$ 的 $dp$：

$$p_{i,j} = p_{i-j,j} + p_{i,j-1}$$

两者的意思分别为：将 $j$ 个 自然数同时 $+1$、加入一个 $0$ 到可重集中。

不难发现这样的确可以不重不漏地计数。

再考虑优化：我们构造一个多项式为：

$$F_i(x)=p_{0,i}+p_{1,i}x+p_{2,i}x^{2}+p_{3,i}x^{3} \dots $$

那么根据上面的转移，我们有：

$$F_i(x) = F_{i-1}(x) \times (1+x^i+x^{2i}+x^{3i}\dots) $$$$F_i(x) = \frac{F_{i-1}(x)}{1-x^{i}}$$

那么也就不难得到：

$$F_{i}(x) = \prod_{j=1}^{i} \frac{1}{1-x^{j}}$$

这个东西和 付公主的背包 是一样的。具体做法就是求 $\ln$ ，加起来再 $\exp$ 回去，最后求个逆就完了。

考虑这个东西如何快速求 $\ln$：

$$G(x) = \ln (1-x^{i})$$ $$G'(x) = \frac{-ix^{i-1}}{1-x^{i}}$$ $$G'(x) = (-ix^{i-1}) \times \frac{1}{1-x^{i}}$$ $$G'(x) = (-ix^{i-1}) \times \sum_{j=0}^{\infty} x^{ij} $$$$G'(x) = -\sum_{j=1}^{\infty} ix^{ij-1}$$ $$G(x) = -\sum_{j=1}^{\infty} \frac{x^{ij}}{j}$$

然后在模 $x^{n+1}$ 意义下做这个东西就完事了。

十一、球相同，盒子相同，每个盒子至多装一个球

和第五个是一样的东西，就是 $[n\leq m]$。

十二、球相同，盒子相同，每个盒子至少装一个球

考虑就是将上面的“划分数”中的自然数变成正整数，我们强制现在每个盒子里头放一个球，就是同样的问题了。答案即为 $p_{n-m,m}$。

完整代码 比较长，这里略去多项式板子以及基础数论部分的代码（因为用的是 vim，所以可能有很多折叠标记）

/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more scores.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }
//}}}

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }

const int MAXN = 530010;
const int mod = 998244353;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }

int n, m;

int fac[MAXN];
int inv[MAXN];
int ifac[MAXN];

int tN;
int N, InvN;
int p[MAXN];
int G[MAXN];
int S[MAXN];
int F[MAXN];

int A[MAXN];
int B[MAXN];
int tA[MAXN];
int tB[MAXN];
int tC[MAXN];
int tD[MAXN];

//{{{ Math And Prework
inline int fsp(int x, int k = mod - 2) {}// 快速幂
inline int C(int n, int m) {} // 组合数
inline void Combine_init(int n) {} // 预处理阶乘以及逆元
inline void Prework() {} // 预处理原根
inline void NTT_init(int n) {}
inline void NTT(int a[], int k) {} // 快速数论变换
inline void GetInv(int A[], int B[], int n) {} // 多项式求逆
inline void GetLn(int A[], int B[], int n) {} // 多项式求对数
inline void GetExp(int A[], int B[], int n) {} // 多项式 exp

inline void init(int n, int m) {
	Prework(), Combine_init(n + m), NTT_init(max(n, m));
    
	for(int i = 0; i <= n; i++) {
		A[i] = i & 1 ? mod - ifac[i] : ifac[i];
		B[i] = 1LL * fsp(i, n) * ifac[i] % mod;
	} NTT(A, 1), NTT(B, 1);
	for(int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % mod;
	NTT(A, -1);
	for(int i = 0; i <= n; i++) S[i] = A[i]; // 第二类斯特林数
    
	memset(A, 0, sizeof(A));
	for(int i = 1; i <= m; i++)
		for(int j = i; j <= n; j += i)
			Add(A[j], mod - inv[j / i]);
	memset(B, 0, sizeof(B)), GetExp(A, B, n + 1);
	memset(A, 0, sizeof(A)), GetInv(B, A, n + 1);
	for(int i = 0; i <= n; i++) F[i] = A[i]; // p_{i, m}
}
//}}}

//{{{ solve01
inline int solve01() { return fsp(m, n); }
//}}}

//{{{ solve02
inline int solve02() {
	int res = 1;
	for(int i = 0; i < n; i++)
		res = 1LL * res * (m - i) % mod;
	return res;
}
//}}}

//{{{ solve03
inline int solve03() {
	int res = 0;
	for(int i = 0; i < m; i++)
		res = (res + 1LL * (i & 1 ? mod - C(m, i) : C(m, i)) * fsp(m - i, n)) % mod;
	return res;
}
//}}}

//{{{ solve04
inline int solve04() {
	int res = 0;
	for(int i = 1; i <= m; i++) Add(res, S[i]);
	return res;
}
//}}}

//{{{ solve05
inline int solve05() { return n <= m; }
//}}}

//{{{ solve06
inline int solve06() { return S[m]; }
//}}}

//{{{ solve07
inline int solve07() { return C(n + m - 1, m - 1); }
//}}}

//{{{ solve08
inline int solve08() { return C(m, n); }
//}}}

//{{{ solve09
inline int solve09() { return C(n - 1, m - 1); }
//}}}

//{{{ solve10
inline int solve10() { return F[n]; }
//}}}

//{{{ solve11
inline int solve11() { return n <= m; }
//}}}

//{{{ solve12
inline int solve12() { return n >= m ? F[n - m] : 0; }
//}}}

int main() {
#ifdef LOCAL
	FILE("");
#endif
	n = ri, m = ri, init(n, m);
	cout << solve01() << endl;
	cout << solve02() << endl;
	cout << solve03() << endl;
	cout << solve04() << endl;
	cout << solve05() << endl;
	cout << solve06() << endl;
	cout << solve07() << endl;
	cout << solve08() << endl;
	cout << solve09() << endl;
	cout << solve10() << endl;
	cout << solve11() << endl;
	cout << solve12() << endl;
	return 0;
}