标签 FFT & NTT 下的文章
- 首页
- FFT & NTT
洛谷4233 射命丸文的笔记
Luogu 分析 先考虑所有 $n$ 个点竞赛图的哈密顿回路数之和。可以发现为 多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #includ...
洛谷6295 有标号 DAG 计数
Luogu 分析 设 $f_i$ 为 $i$ 个点的 DAG 数量。 一个想法是枚举入度为 $0$ 的点的数量，有 多项式求逆即可。 现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blo...
洛谷4491 [HAOI2018]染色
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到 可以发现是一个差卷积的形式，于是直接 NTT 即可。 代码 // ===============...
CF438E The Child and Binary Tree
Codeforces Luogu 分析 设 $s_i$ 表示 $i$ 是否在集合中，$f_i$ 表示权值和为 $i$ 的二叉树数量，那么 多项式开根+多项式求逆即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =========...
洛谷4841 [集训队作业2013]城市规划
Luogu 分析 设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有 多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-bl...
洛谷4091 [HEOI2016/TJOI2016]求和
Luogu LOJ 分析 后面显然是卷积的形式，直接 NTT 即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/std...
LOJ6503 「雅礼集训 2018 Day4」Magic
LOJ 分析 容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
LOJ575 「LibreOJ NOI Round #2」不等关系
LOJ 分析 假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为 边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。 代码 // =================================== // author: M_sea // website:...
AGC005F Many Easy Problems
AtCoder Luogu 分析 设要求的东西是 $f_i$，考虑怎么求这个东西。 可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为 可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。 代码 // =================================== // ...