ZigZagK的博客
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$ 取模。...