[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解
题目概述有 $n$ 种颜色的膜法卡，每种颜色有 $a_i$ 种，总共有 $m$ 张。现在要把所有卡片排成一排，如果相邻两个卡片颜色相同则产生一个膜法对，求膜法对个数为 $k$ 的排列个数...
[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b...
[第二类斯特林数+NTT]BZOJ5093(Lydsy1711月赛)【图的价值】题解
题目概述一个 $n$ 个点的简单无向图的价值定义为每个点度数 $K$ 次方的和，求所有 $n$ 个点的简单无向图的价值的和。解题报告只需要知道这两个前置姿势，这道题就很可做了：$$
S(n,m)...
[第一类斯特林数+倍增+NTT]Codeforces960G【Bandit Blues】题解
题目概述求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值，从右边会更新 $B$ 次最大值。解题报告第一类斯特林数：$s(n,k)$ 表示把 $n$ 个数分成 $k$ 个圆排列的方案数。...
[伯努利数+拆系数FFT+多项式求逆]51Nod1258【序列求和 V4】题解
题目概述求 $\sum_{i=1}^{n}i^K,K\le 50000$ 。解题报告同51Nod1228，只不过 $K\le 50000$ 所以不能 $O(K^2)$ 处理伯努利数，于是我们根据...
[FMT]WC2018【州区划分】题解
解题报告搜FMT搜到这道题，其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积，他是这样的：$$
h_s=\sum_{A\subset...
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变成 $2^n-1$ 的期望时间。解...
[cdq分治+NTT]洛谷4721【分治 FFT】题解
题目概述给出 $g$ 以及 $f(0)=1$ ，求：$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的，结果搜分治FFT就搜到这个了，于是填...
[原根+NTT+快速幂]BZOJ3992(SDOI2015)【序列统计】题解
题目概述有 $S$ 个数，取 $n$ 次（可重复取），将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成NTT就行了。我原来以为这道题是循环...
[思维+FFT]BZOJ4259【残缺的字符串】题解
题目概述有两个串 $A,B$ ，有些位置是通配符，求 $A$ 可以在 $B$ 的哪些位置匹配。解题报告早就听说了这题，今天来填坑。判断两个字符串相等可以用式子：$\sum_{i=0}^{len}...
