我们可以通过生成函数 + 卷积来解决一系列划分数问题,同理,循环卷积就是帮助我们解决取模意义下的部分划分数问题的工具。

CF1096G Lucky Tickets ▷ 2019-01-13

定义生成函数 f

f(x) = \sum\limits_{i=0}^{\infty} tag(i) \times x^i

若集合中有 i 则,tag(i) = 1 ;否则 tag(i) = 0

[x^i]f^n(x) 表示选 n 项时和为 i 的方案数。

容易发现答案即:

\sum\limits_{i=0}^{\infty} ([x^i] f^n(x))^2

洛谷3321 [SDOI2015]序列统计 ▷ 2019-01-13

与上一题不同的是,本题是 \bmod m 意义下的乘法,所以我们可以把原来的乘法转换为与 m 的原根的对数的加法,再用类似的思路即可。

定义生成函数 f

f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i

其中 tag(i) = 1 当且仅当存在 x \in S 使得 \log_g x = i

最后答案为: [x^k]f^n(x)

NTT 循环卷积

特征多项式和常系数线性齐次递推学习笔记
上一篇 «
Polya 定理学习笔记
» 下一篇