版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Luogu P5824] 十二重计数法" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• 洛谷
• 数学
• 组合数学
• 计数
• 排列
• 反演
• 二项式反演
• 第二类Stirling数
• 多项式
• 卷积
• 生成函数
• 普通生成函数
• 隔板法 date: 2023-05-01 00:45:37

题目链接

原始题面

题目背景

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

传说早在 $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}$: 球全部相同, 盒子全部相同, 每个盒子至少装一个球.

由于答案可能很大, 所以要对 $998244353$ 取模.

输入格式

仅一行两个正整数 $n,m$

输出格式

输出十二行, 每行一个整数, 对应每一种限制条件的答案.

样例 #1

样例输入 #1

13 6

样例输出 #1

83517427
0
721878522
19628064
0
9321312
8568
0
792
71
0
14

提示

【数据范围】
对于 $100\%$ 的数据, $1\le n,m \le 2\times 10^5$.

orz $\mathsf E \color{red}\mathsf{ntropyIncreaser}$

解题思路

Ⅰ

不难发现答案即为 $m^n$

Ⅱ

不难发现答案即为 $m^{\underline{n}}$

Ⅲ

考虑二项式反演

设

• $f(n,m)$ 为 $n$ 个球和 $m$ 个盒子, 球之间互不相同, 盒子之间互不相同, 每个盒子至少装一个球的方案数
• $g(n,m)$ 为 $n$ 个球和 $m$ 个盒子, 球之间互不相同, 盒子之间互不相同的方案数

则

$$ \begin{aligned} &m^n=g(n,m)=\sum{i=0}^m\binom{m}{i}f(n,i)\ \implies &f(n,m)=\sum{i=0}^m\binom{m}{i}(-1)^{m-i}g(n,i)=\sum_{i=0}^m\binom{m}{i}(-1)^{m-i}i^n \end{aligned} $$

Ⅳ

考虑第二类 Stirling 数, 不难发现答案为

$$ \sum_{i=0}^m{n \brace i} $$

使用卷积可以快速求出答案, 具体而言, 令

• $$ f(x)=\sum_{i=0}^{\infty}\frac{i^n}{i!}x^i $$
• $$ g(x)=\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}x^i $$

则

$$ h(x)=f(x)g(x)=\sum{i=0}^{\infty}x^i\sum{j=0}^i\frac{(-1)^{i-j}j^n}{j!(i-j)!}=\sum_{i=0}^{\infty}{n\brace i}x^i $$

Ⅴ

不难发现当 $m<n$ 时答案为 $0$, 否则为 $1$

Ⅵ

考虑第二类 Stirling 数, 不难发现答案为 ${n \brace m}$

可以和 Ⅳ 一起求

Ⅶ

考虑隔板法, 不难发现答案为 $\binom{n+m-1}{m-1}$

Ⅷ

不难发现答案即为 $\binom{m}{n}$

Ⅸ

考虑隔板法, 不难发现答案为 $\binom{n-1}{m-1}$

Ⅹ

设 $f(n,m)$ 为所求, 则

$$ f(n,m)=f(n,m-1)+f(n-m,m) $$

考虑 OGF

$$ \begin{aligned} &\begin{aligned} Fm(x)&=\sum{i=0}^{\infty}f(i,m)x^i\ &=F_{m-1}(x)+x^m F_m(x) \end{aligned}\ \implies& Fm(x)=\frac{1}{1-x^m}F{m-1}(x)\ \implies& Fm(x)=\prod{i=1}^{\infty}\frac{1}{1-x^i}\ \implies& \ln Fm(x)=-\sum{i=1}^{\infty}\ln(1-x^i)\ \implies& \ln Fm(x)=\sum{i=1}^{\infty}\sum_{j=1}^{\infty} \frac{x^{ij}}{j}\ \implies& Fm(x)=\exp\left(\sum{i=1}^{\infty}\sum_{j=1}^{\infty} \frac{x^{ij}}{j}\right) \end{aligned} $$

Ⅺ

同 Ⅴ

Ⅻ

类似 Ⅹ, 答案为 $f(n-m,m)$

代码参考