洛谷4491 [HAOI2018]染色
LuoguLOJ分析显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到可以发现是一个差卷积的形式，于是直接 NTT 即可。代码// =======================...
标签 FFT & NTT 下的文章
- 首页
- FFT & NTT
CF438E The Child and Binary Tree
CodeforcesLuogu分析设 $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-blog.com...
洛谷4091 [HEOI2016/TJOI2016]求和
LuoguLOJ分析后面显然是卷积的形式，直接 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h&...
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: https...
洛谷5641 【CSGRound2】开拓者的卓识
LuoguKarry is God !!!分析考虑 $a_i$ 对 $sum_{k,1,r}$ 的贡献。显然左右独立，因此只考虑计算左边的方案数，即在 $i$ 个位置中放 $k-1$ 个左端点，因而左边的方案数为 $i+k-2\choose k-1$。类似地可以得到右边的方案数为 $r-i+k-1\choose k-1$。从而得到这样子就可以直接 NTT 了。需要注意的是这个组合数是不太能直...
AtCoder Grand Contest 005 简要题解
比赛地址STring和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。代码Minimum Sum单调栈板子题。代码Tree Restoring首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：若 $d$ 为奇数，则应有 考虑计算 $f_i$。容易发现一...
AGC005F Many Easy Problems
AtCoderLuogu分析设要求的东西是 $f_i$，考虑怎么求这个东西。可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。代码// =================================== // author: ...
洛谷4199 万径人踪灭
LuoguBZOJ分析下文中默认字符串的下标从 $0$ 开始。可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。后面的就是 manacher 板子，考虑怎么求前面的。设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1$，累加起来即可...