cdq分治FFT
非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq分治，先处理 $[L,mid]$ ...
拉格朗日插值
求多项式我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要求 $f(k)$ ，可以先解出 $...
Min_25筛
一类问题已知积性函数 $f(n)$ ，其中 $f(p)$ 是简单多项式，且 $f(p^k)$ 可以快速计算（ $p$ 是素数），求其前缀和。上杜教筛？如果 $f(n)$ 很奇怪就没法卷另外一个...
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造，导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
[伯努利数]51Nod1228【序列求和】题解
题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着，但是 $n$ 太tm大了，不过 $K$ 很小，所以要想办法搞成只和 $...
[FMT]BZOJ4036(HAOI2015)【按位或】题解
题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变成 $2^n-1$ 的期望时间。解...
[Miller-Rabin+Pollard-Rho]Codeforces1025B【Weakened Common Divisor】题解
题目概述有 $n$ 组数对 $(a_i,b_i)$ ，求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。解题报告因为随便求所以找共有的素因子就好了，那么先求出 $GCD$ ...
NTT
快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 $A(x)B(x)$ ，只不过系数要对 $p$ 取模。...
