LOJ150 - 挑战多项式

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

洛谷4841 - 城市规划

想 LJC00118 NOIP 考前就秒切了这题,memset0 又又又被吊打.jpg

考虑有标号无向图的生成函数:$f(x) = \sum\limits_{i=0}^{\infty} 2^{n \choose i} \frac{x^n}{n!} $。

考虑有标号无向联通图的生成函数 $g(x)$ ,容易证明 $exp(g(x)) = f(x)$ 。

此题需求 $g(x)$ ,那么直接多项式 $\ln$ 即可。

洛谷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}
$$

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 一波即可。

设 $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!

CF1096G - Lucky Tickets

一道生成函数板题,定义生成函数 $f$:
$$
f(x) = \sum\limits_{i=0}^{\infty} tag(i) \times x^i
$$

若集合中有 $i$ 则,$tag(i) = 1$ ;否则 $tag(i) = 0$ 。

则 $[x^i]f^n(x)$ 表示选 $n$ 项时和为 $i$ 的方案数。

容易发现答案即:

$$
\sum\limits_{i=0}^{\infty} ([x^i] f^n(x))^2
$$

多项式快速幂即可。

20181210 - NOI模拟赛

T3 难度并不大,但是由于时间分配问题 + 出题人数据有锅必须输出行末空格否则 WA 导致本来会做的 T3 没有 AC 。

迷路

对于每一个点,建出最短路树,对于每一条非树边,如果他的两个节点在根节点的不同子树内,那么可以对答案产生贡献。

宝藏

类欧优化的数学题,不会。

蛋糕

THUPC 原题的强化版,由 $4$ 维变成 $n$ 维。每一维变成一个多项式分治 NTT 即可。

Your browser is out-of-date!

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

×