标签 NTT 下的文章

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

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

多项式乘法

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

READ MORE

P(S) 为钦点 S 中所有元素都在 1 之后挂掉的概率,显然:

P(s) = \frac{a_1}{sum(S) + a_1}

于是我们可以发现最后答案为:

ans = \sum\limits_{S \in [2, n]} P(S) (-1)^{|S|}

于是分治 + NTT 即可。

至此除斗地主外的所有 PKUWC 2018 题目已经订正完毕,祝也去参加 PKUWC 的读者和自己 RP = +\infty qwq!

READ MORE