洛谷4091 [HEOI2016/TJOI2016]求和
LuoguLOJ分析后面显然是卷积的形式，直接 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h&...
标签 FFT & NTT 下的文章
- 首页
- FFT & NTT
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$，累加起来即可...
Educational Codeforces Round 75 题解
Broken Keyboard如果某一段相同的字符长度为奇数，那么这个字符一定是正常的。代码Binary Palindromes一个长度为偶数的回文串一定有偶数个 $1$，一个长度为奇数的回文串可以有任意个 $1$。检查 $1$ 的奇偶性，如果为偶数则答案为 $n$；否则，如果有长度为奇数的回文串则答案为 $n$，否则答案为 $n-1$。代码Minimize The Integer注意到奇偶...