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!

与上一题类似,我们可以考虑生成函数。但是由于本题是 $\mod m$ 意义下的乘法,所以我们可以把原来的乘法转换为与 $m$ 的原根的对数的加法。再用上题目类似的思路即可。

定义生成函数 $f$ :

$$
f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i
$$

其中 $tag(i) = 1$ 当且仅当存在 $x \in S$ 使得 $\log_g x = i$ 。

最后答案为:

$$
[x^k]f^n(x)
$$

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

多项式快速幂即可。

BZOJ4178 - A

今天模拟赛的第一题, NTT 作多项式乘法,把后面的转移快速幂一下就过了。需要注意的是 950009857 的原根是 7 而不是 3 。

分治套 NTT 优化仙人掌 DP 题目。往这个方向想其实不是很难推,于是就懒得写题解直接贴代码了 qwq。

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

×