A

不解释

B

不解释

C

石头剪刀布大模拟...

不解释

D

类似于货币系统,背包转移即可。

E

设每一条边被经过了多少次为 $c_i$,设有红蓝边各 $R$ 条,$B$ 条,那么很容易得到:

$R+B = \sum c_i, R-B = k$

可以直接解得:$R = \frac{\sum c_i + k}{2}, B = \frac{\sum c_i - k}{2}$

那么红蓝边各要染多少已经直接解出来了($c_i$ 可以在 $O(n^2)$ 的时间内预处理),问题转化成:有红蓝物品各 $R,B$ 个,有 $n-1$ 个背包,第 $i$ 个容量为 $c_i$(强制 $c_i \geq 1$ 的必须选一个),求方案数。

然后还是背包转移就行了。

Code: Code

F

首先假如只从一个点出发,比如说 $1$ ,那就是计算以 $1$ 为根的子树的答案,DP 非常好做。现在是要求 $n$ 个的,看看能不能换根 DP

官方题解里面对换根 DP 的使用方法总结的不错,记录在这里:

  1. DP 状态的值的类型
  2. 在某一个点合并的方式和关键贡献
  3. 计算当根转移到子节点时没有当前根的贡献(也就是关键贡献)

那么原来我们可以设 $f_u$ 表示以 $u$ 为根的子树答案,转移 :$f_u = \max\limits_{v \in son_{u} } \{max(d_v, f_v) + w(u,v)\}$

我们可以在以 $1$ 为根的时候,记录每一次 $f_u$ 是从哪一个 $v$ 转移过来的,那么每次需要消除的关键贡献就是那个点的答案。

Code: Code

G

首先想到把 $222\dots222$ 这种数字拆开来,假如有 $n$ 位,数为 $s$ ,那么:

$$ s = \sum\limits_{i=0}^{n-1} 10^{i} \cdot 2 $$

可以等比数列求和,顺便复习一下等比数列求和公式,设首项为 $a$,公比为 $q$,项数为 $m$,那么 $sum = \frac{a(1 - q^n)}{1-q}$

所以 $s = \frac{2(10^n-1)}{9}$

那么现在问题就转化成了:要找到最小的 $n$ ,使得 $s \equiv 0 \mod {K}$

复习同余中的两个定理:

  1. $\frac{x}{b} \equiv 0 \mod M \Longleftrightarrow x \equiv 0 \mod bM$
  2. $ax \equiv 0 \mod M \Longleftrightarrow x \equiv 0 \mod \frac{M}{\gcd(a, M)}$

先转化一波式子,先用第一个式子,把分母中的 $9$ 移过去:$2(10^n-1) \equiv 0 \mod 9M$

再用第二条,发现 $gcd(a,M)$ 就是对 $M$ 的奇偶性进行讨论:

$$ M'= \left\{ \begin{aligned} 9M , M \equiv 0 \mod 2 \\ \frac{9M}{2}, M \equiv 1 \mod 2 \end{aligned} \right. $$

所以现在要求的就是:$(10^n-1) \equiv 0 \mod M'$ 的最小的 $n$

再稍微换一下:$10^n \equiv 1 \mod M'$

因为 $\gcd(1, M') = 1$ ,根据欧拉定理则:$10^{\phi(M')} = 1 \mod M'$

猜想一下, $n$ 是 $\phi(M')$ 的约数是合法答案。

证明:

若 $n$ 不是 $\phi(M')$ 的约数,设 $n > d = \gcd(n, M')$,有:$pn + q\phi(M') = d$ ,则:$10^d = (10^n)^a(10^{\phi(M')})^q \equiv 1 \mod M'$ ,故存在 $d < n$ 满足题意与假设矛盾,所以 $n$ 是 $\phi(M')$ 的约数。

所以可以 $O(\sqrt{M'})$ 的时间内算出 $\phi(M')$ 和 $M'$ ,然后判断即可。

H

多项式?生成函数?

不更

最后修改:2021 年 10 月 19 日
如果觉得我的文章对你有用,请随意赞赏