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 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏