LOJ150 - 挑战多项式

这题非常的水,我们拉个板子就 A 掉了 …

洛谷5162 - WD与积木

用 $f_i$ 表示 $i$ 个时的高度之和, $g_i$ 表示 $i$ 个时的方案数,显然:

$$
\begin{align}
g_n &= \sum\limits_{i=1}^n {n \choose i} g_{n-i} \\
f_n &= g_n + \sum\limits_{i=1}^n {n \choose i} f_{n-i} \\
ans_n &= f_n \times g_n^{-1}
\end{align}
$$

其实到这里可以直接分治 NTT ,不过我们考虑多项式求逆的做法。
首先把 ${n \choose i}$ 拆开,然后设 $F_n = f_n / n!$ , $G_n = g_n / n!$ , $H_n = 1 / n!$ 则

$$
\begin{align}
G &= (2 - H)^{-1} \\
F &= (G - 1) (2 - H)^{-1} \\
ans_n &= F_n G_n^{-1}
\end{align}
$$

(推导时需要注意常数项系数,$f_0 = 0,g_0 = h_0 = 1$。)

分治 NTT 学习笔记

memset0 又来水博客了…

第一种做法是正常的分治 NTT ,想必大家都会,就不废话了;
第二种做法是多项式求逆,想必大家也会,就摆几个式子了。

令 $F = \sum\limits_{x=0}^{\infty} x^i f_i$ , $G = \sum\limits_{x=0}^{\infty} x^i g_i$ ,则易得 $F * G = F - 1$ ,故 $F = (1 - G)^{-1}$ ,多项式求逆即可。

多项式求逆学习笔记

其实这玩意儿之前学过,不过感觉挺有趣的就再拿出来写篇笔记。

$$
\begin{align}
A B_n &\equiv 1 \pmod {x^n} \\
A B_{\frac n2} &\equiv 1 \pmod {x^{\frac n2}} \\
\\
B_n - B_{\frac n2} &\equiv 0 \pmod {x^{\frac n2}} \\
B_n^2 - B_n B_{\frac n2} + B_{\frac n2}^2 &\equiv 0 \pmod {x^n} \\
A(B_n^2 - 2B_n B_{\frac n2} + B_{\frac n2}^2) &\equiv 0 \pmod {x^n} \\
B_n &\equiv 2B_{\frac n2} - AB_{\frac n2}^2 \pmod {x^n}
\end{align}
$$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×