洛谷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$ 即可。

大于 $\max(c_i c_j)$ 的 $ v = \gcd(c_i) \ (i \in [1, n])$ 的倍数都可以被取到。
先做关于 $v$ 的循环卷积,然后背包一下把中间相差的部分补上即可。
由于要求对 $10^9+7$ 取模,所以需要 MTT。

与上一题类似,我们可以考虑生成函数。但是由于本题是 $\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
$$

多项式快速幂即可。

Your browser is out-of-date!

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

×