PKUWC 考挂的我只能争取省选翻盘了。

从寒假开始就没有再颓废过游戏了,唯一浪费时间的可能就是干了些工程向的东西。基本 follow 着 txc 和 zsy 的博客做题,有时旷掉考试

不知道这样的训练是否有用呢,ZJOI 会告诉我答案吧。

READ MORE

ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

READ MORE

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k])步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

READ MORE

写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

READ MORE