ZigZagK的博客
[并查集]洛谷6786【GCDs & LCMs】题解
题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ,然后推式子:$$ BA+CA+A={BA\cdot CA\over A}\\ BA+C...
[多项式多点求值]洛谷5050【多项式多点求值】题解
题目概述给出一个多项式 $F(x)$ ,有 $m$ 个询问,每次求 $F(a_i)$ 。解题报告将 $F(x)$ 在 $x=a$ 处进行泰勒展开:$$ F(x)=F(a)+F'(a)(x-a)+...
[多项式exp]洛谷4726【多项式指数函数】题解
题目概述求 $B(x)=e^{A(x)}\ mod\ x^n$ 。解题报告前置姿势:多项式求逆,多项式ln。第一种方法是两边求导:$$ B'(x)=e^{A(x)}A'(x)\\ B'(x)=B...
[多项式ln]洛谷4725【多项式对数函数】题解
题目概述求 $B(x)=lnA(x)(mod\ x^n)$ ,即满足 $A(x)=e^{B(x)}$ 。解题报告前置姿势:多项式求逆,多项式求导,多项式积分。多项式求导:就是对每项分别求导:$(...
[多项式除法]洛谷4512【多项式除法】题解
题目概述给出多项式 $A(x),B(x)$ ,求 $C(x),D(x)$ 满足 $A(x)=C(x)B(x)+D(x)$ 。解题报告显然求出 $C(x)$ 或 $D(x)$ 就能求出另外一个,所...
[多项式开根]洛谷5205【多项式开根】题解
题目概述给出一个多项式 $A(x)$ ,求 $B(x)$ 使得 $B^2(x)\equiv A(x)(mod\ x^n)$ ,保证 $A(x)_0=1$ 。解题报告前置姿势:多项式求逆。还是考虑...
[扩展Min-Max容斥+DP]洛谷4707【重返现世】题解
题目概述有 $n$ 种物品,每单位时间出现 $i$ 物品的概率为 $p_i$ ,求恰好出现 $K$ 个不同物品的期望时间。解题报告Min-Max容斥?但是出现 $K$ 个是什么鬼啊。这里要用到扩...
[FMT]WC2018【州区划分】题解
解题报告搜FMT搜到这道题,其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积,他是这样的:$$ h_s=\sum_{A\subset...
[cdq分治+NTT]洛谷4721【分治 FFT】题解
题目概述给出 $g$ 以及 $f(0)=1$ ,求:$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的,结果搜分治FFT就搜到这个了,于是填...
[莫比乌斯函数+调和级数]洛谷U32290【LJJ爱数数】题解
题目概述求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。解题报告被学弟安利了这题(学弟秒掉了来嘲讽我)。...