[NTT]Codeforces528D【Fuzzy Search】题解
题目概述CF528D解题报告奇怪的字符串匹配，并且字符集很小，考虑卷积。对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i+K]$ 这些位置都可以匹配。令 ...
[多项式ln+多项式exp+分治NTT]LOJ2320【「清华集训 2017」生成树计数】题解
题目概述LOJ2320解题报告学到了好多多项式套路。如果 $i$ 连通块度数是 $d_i$ ，则每条边都有 $a_i$ 个选择，把 $a_i$ 放进答案式子里，答案式子就是：$$
\sum_T(...
[容斥+分治NTT]LOJ575【「LibreOJ NOI Round #2」不等关系】题解
题目概述LOJ575解题报告有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前缀和后缀和是没有办法加速的，复杂度...
[分治NTT+倍增]2022 CCPC 桂林 D【Alice's Dolls】题解
题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品，$x^k$ 的期望。$n>1$ 的情况十分复杂，但是根据期望的线性性，$n>1$ 的情...
[单位根反演+Bluestein套路]LOJ3058【「HNOI2019」白兔之舞】题解
题目概述LOJ3058解题报告这个 $m\bmod k=t$ 以及 $k$ 是 $MOD-1$ 因子显然是单位根反演，所以考虑用生成函数表示答案。令转移矩阵为 $M$ ，定义 $F_i(x)$ ...
cdq分治FFT
非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq分治，先处理 $[L,mid]$ ...
[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后：$$
{t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[NTT]AtCoder Grand Contest 005F【Many Easy Problems】题解
题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献：$$
\sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{size_j\choose k}]=...
[DP+分治NTT]HDU5322【Hope】题解
题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后对于 $n$ 右边的数列也可以递归...
[容斥+分治NTT]LOJ2541【「PKUWC2018」猎人杀】题解
题目概述LOJ2541解题报告可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死人开枪（但没有效果），问最后才打死...
