洛谷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}$ ,多项式求逆即可。

CF1043F - Make It One

考虑加入一个数如果不能使公因数减少,则可以不放。计算可得答案必定 $\leq 7$。又发现不能直接对存在性进行容斥,容斥方案数即可。

($cnt_i$ 表示以 $i$ 为因数的数的个数,$f_i$ 表示选 $ans$ 个数使得公因数为 $i$ 的方案数。)

多项式求逆学习笔记

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

$$
\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}
$$

AT2064 - Many Easy Problems

容斥可得:

$$
ans_k = n {n \choose k} - \sum\limits_{u=1}^n ({n - siz_u\choose k} + \sum\limits_{v \in son_u} {siz_v \choose k})
$$

NTT 一波即可。

数据范围容易想到利用矩阵进行计算。

考虑 $f(k) = (A, B)$ ,其中 $A$ 表示恰好等于 $k$ 的路径条数, $B$ 表示小于等于 $k$ 的路径条数。则可以这样转移: $(A, B) \times (C, D) = (A \times C, B + A \times D)$ 。

需要注意的是,对长度为 $L$ 的路径对答案的贡献可以表示为一个二次多项式(即 $f(L) = L ^ 2$),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

SAM 板子题。

可以发现两个串的 LCS 即在 SAM 上的 LCA 的 len ,对于每一个点统计对答案的贡献次数即可。

Min_25 筛板子题。

注意一些需要开 long long 的地方。

PKUWC 2019 游记

谨以此文记录我的 OI 生涯的第一次向 PKU 冲刺的机会。

持续更新。

最近有人用脚本(或其他)方式在这个博客刷大量垃圾评论骚扰。我有一些内容想留给那位同学:

Your browser is out-of-date!

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

×