LOJ150 - 挑战多项式

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

前置知识 Polya 定理。

会了以后推一下式子,得

$$
\begin{aligned}
ans &= \sum_{i=1}^n n^{\gcd(i, n)} \\
&= \sum_{d|n} n^d \varphi(\frac nd)
\end{aligned}
$$

直接做即可。没错我就是来水题解的

CF1105E - Helping Hiasat

可以发现,在两个 1 操作之间的人中最多满足一个。我们可以两两连边,这样问题就转换为最大独立集问题,按照套路此时我们作补图,将最大独立集转换为求补图最大团

最大团的常用算法是 Bron Kerbosch ,我们甚至不需要很强的优化剪枝就可以过掉这题。

CF1100F - Ivan and Burgers

一道线性基傻逼题。然而我一开始智商掉线连写了两个假算法。

首先这题三只 $\log$ 肯定是过不去的,除非你是 wys
然后也不能用多个线性基来更新一个答案。

上面都是废话,直接整体二分就过了。

洛谷3601 签到题

这题非常的签到。

考虑到一个数只能被小于根号的质数筛到,暴力做即可。

复杂度为 $O(n \log n)$ ,其中 $n = r - l + 1$ 。

洛谷5029 - T'ill It's Over

做那么多水题,会不会被婊…

还是网络流,只不过这次我们需要从一个区间连到另一个区间,那么就是个典型的线段树优化建边。
需要注意一些小细节。

网络流裸题,没什么好说的。
需要注意的是,我们在给厨师拆点的时候,如果先把边都连好,时间是会炸掉的。所以我们就没“用掉”一个厨师新建一次点即可。

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

CF1043F - Make It One

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

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

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 的地方。

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

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

洛谷4839 - P哥的桶

每个点维护线性基,线段树的两个子节点合并的时候直接把一个点的暴力插入到隔壁即可。

考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

同理可 Min-Max 容斥:

$$
\min(S) = \frac{1}{1 - \sum\limits_{S’ \subseteq S} \sum\limits_{u \in S’} p_u}
$$

FWT 一波即可。

HDU4336 - Card Collector

考虑 Min-Max 容斥。用 $\min(S)$ 表示 $S$ 中出现至少一个元素的期望时间,用 $\max(S)$ 表示 $S$ 中每一个元素都出现的期望时间。

则:

$$
\begin{aligned}
\min(S) &= \frac{1}{\sum\limits_{i \in S} p_i} \\
\max(S) &= \sum\limits_{S’ \subseteq S} \min(S’) (-1)^{|S’| - 1}
\end{aligned}
$$

答案显然是让我们求 $\max(\texttt{全集})$ ,故状压一下即可。

Your browser is out-of-date!

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

×