题解 | 题解E-G

【E】图上替身追赶游戏：

题解：

可以通过手玩一下样例发现，树在加边后会产生一个环，这个环是saki甩开miku的关键。当环的长度分别为4、5、6时，均可以通过一系列操作，使得在某个回合结束时，与miku不再相邻或重合。

也就是说本题可以转化为，计算给定树中长度为3、4和5的简单路径的总数量。代码采用树形动态规划（Tree DP）的思想来解决。（也可以使用换根，分治等方法）

核心思路：

我们通过深度优先搜索（DFS）遍历树，并在DFS的过程中计算和累积路径信息。关键在于定义DP状态以及如何合并子树信息。

其中变量 ans 最终累计了所有长度为3、4、5的简单路径的数量。通过一次DFS遍历，利用 f[d][u] 数组存储子树内距离信息。在回溯时（即子节点DFS结束后），它首先利用当前 f[j][u]（代表“左侧分支”）和 f[k-j][v]（代表“右侧分支”，其中 v 是刚处理完的子节点）来组合路径并更新 ans，然后才将 v 子树的信息整合进 f[][u]，为后续的计算做准备。这种“先计算贡献，再合并信息”的顺序是树形DP中常见的处理方式，确保了每个路径只被计算一次且不会遗漏。

代码解析

from sys import stdin
input = lambda: stdin.readline().rstrip()
 
def solve():
    n, _ = map(int, input().split())
    g = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
 
    f = [[0] * (n + 1) for _ in range(6)]
    ans = 0
    dep = [0] * (n + 1) 
 
    def dfs(u, fa):
        nonlocal ans
        dep[u] = dep[fa] + 1
        f[0][u] = 1
        for v in g[u]:
            if v == fa:
                continue
            dfs(v, u)
            for k in range(2, 5):
                for j in range(k + 1):
                    ans += f[j][u] * f[k - j][v]
            for j in range(5):
                f[j + 1][u] += f[j][v]
     
    dfs(1, 0)
    return ans
 
print(solve())

代码详解:

1. DP状态定义：

f[k][u]：表示在以节点 u 为根的子树中，与节点 u 距离为 k 的节点有多少个。

2. DFS过程详解：

dfs(u, fa) 函数处理以 u 为当前节点，fa 为其父节点的情况。

• 初始化：

  • dep[u] = dep[fa] + 1：计算当前节点 u 的深度（根节点深度为1，其父节点0的深度为0）。
  • f[0][u] = 1：对于节点 u 本身，它与自身的距离为0。所以以 u 为根的子树中，与 u 距离为0的节点只有 u 自己，数量为1。

• 遍历子节点： 对于 u 的每个子节点 v（v != fa）：

  1. 递归调用： dfs(v, u)。这会先计算完成以 v 为根的子树中所有的 f[][v] 值。

  2. 路径统计 (核心部分)： 在从 dfs(v, u) 返回后，我们利用已经计算好的 f[][u]（包含 u 自身以及 u 的 在 v 之前处理过的 其他子树的信息）和 f[][v]（包含 v 的子树信息）来统计经过边 (u,v) 的路径。 我们关注的路径形态是 X - ... - u - v - ... - Y，其中：

     • X 是在 u 的子树中（但在 v 的子树之外，或者是 u 本身）的一个节点。
     • Y 是在 v 的子树中的一个节点。
     • 路径 X - ... - u 的长度为 j。这样的 X 有 f[j][u] 个。
     • 路径 v - ... - Y 的长度为 d。这样的 Y 有 f[d][v] 个。
     • 那么，完整路径 X - ... - u - v - ... - Y 的长度为 j + 1 + d (1代表边 (u,v) 的长度)。

     代码中的循环 for k in range(2, 5): 实际上是在枚举 j+d 的值。

     • 当 k = 2时，我们统计 j+d = 2，总路径长度为 j+d+1 = 3。
     • 当 k = 3时，我们统计 j+d = 3，总路径长度为 j+d+1 = 4。
     • 当 k = 4时，我们统计 j+d = 4，总路径长度为 j+d+1 = 5。

     内层循环 for j in range(k + 1): 枚举了路径 X - ... - u 的长度 j (即 d1)。

     • 那么路径 v - ... - Y 的长度 d (即 d2) 就必须是 k-j。
     • 此时，符合条件的路径数量为 f[j][u] * f[k-j][v]。将这个乘积累加到 ans。
     • 注意：这里的 f[j][u] 尚未包含来自子树 v 的贡献，这正是我们想要的，因为它保证了路径的两个分支分别来自 u 的不同“方向”（一个方向是 v 子树，另一个方向是 u 的其他子树或 u 自身）。

  3. 更新 f[][u]： 在统计完以 v 为一支的路径后，需要将子树 v 的信息合并到 f[][u] 中，以便后续 u 的其他兄弟子树或者 u 的父节点使用。 for j in range(5): f[j + 1][u] += f[j][v] 这条语句的含义是： 如果一个节点 Z 在子树 v 中，且与 v 的距离为 j（这样的节点有 f[j][v] 个），那么节点 Z 与 u 的距离就是 j+1。 所以，我们将 f[j][v] 的值累加到 f[j+1][u] 上。 j 从0到4，意味着 j+1 从1到5。这对应了 f 数组的维度。

• DFS起始： dfs(1, 0) 从节点1开始DFS，假设节点0是节点1的虚拟父节点，其深度为0。

复杂度分析

• 时间复杂度：O(6n)。
• 空间复杂度：O(n)。

【F】奇素数回路：

题目描述

我们需要构造一个由 1 到 n 这 n 个不同整数构成的环形数组 a（其中 n 为偶数，下标从0开始），使得环形数组中任意相邻两项的差的绝对值为一个【奇素数】。如果无法构造，则输出 -1。

解题思路

出题人本身的构想是通过构造奇素数回路在8,10,12,14的情况，然后通过把多个回路进行组合，从而完成构造。然而某一天出题人在摸鱼的时候发现，可以限制奇素数的种类数，只用两个不同的奇素数就可以完成构造，甚至这种加强版的题目反而更加简单，下文会介绍这种方法。

代码的整体思路是先通过筛法预处理出一定范围内的所有素数，然后尝试找到一个奇素数 p，使得 n-p 也是一个奇素数。如果能找到这样的两个奇素数 p 和 q = n-p，则可以构造出满足条件的环形数组。这个是通过对一些比较小的 n的构造的过程中发现的，后文有素数对存在性和构造数字唯一性的证明。

比如 n=8，可以构造成 [1,4,7,2,5,8,3,6]，相邻两项的差的模都是3是素数，8-3=5也是素数;

1+3=4,4+3=7,7+3=10【2(mod8)】,2+3=5,5+3=8,8+3=11【3(mod8)】,3+3=6,6+3=9【1(mod8)】

n=10，可以构造成 [1,4,7,10,3,6,9,2,5,8]，相邻两项的差的模都是3是素数，10-3=7也是素数;

n=12，可以构造成 [1,6,11,4,9,2,7,12,5,10,3,8]，相邻两项的差的模都是5是素数，12-5=7也是素数。

代码解析

MX = 10 ** 5 + 1
primes = []
is_prime = [True] * MX
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False
primes = primes[1:]

for i in [0, 1, 2]:
    is_prime[i] = False

def solve(n):
    if n < 8:
        return -1

    for p in primes:
        if p >= n:
            break
        if is_prime[n - p]:
            ans = [1]
            for i in range(n - 1):
                ans.append((ans[-1] + p - 1) % n + 1)
            return " ".join(map(str, ans))

    return -1

for _ in range(int(input())):
    n = int(input())
    print(solve(n))

代码详解:

1. 预处理素数

• 代码首先使用标准的欧拉筛法（Sieve of Eratosthenes）找出 MX = 10^5 + 1 范围内的所有素数，并存储在 primes 列表中。
• is_prime 数组用于标记一个数是否为素数。
• primes = primes[1:] 这一步移除了列表中的第一个素数 2，因为题目要求差为【奇素数】，所以 2 不符合作为差值的情况。
• is_prime[0], is_prime[1], is_prime[2] 被显式标记为 False。这确保了后续在检查 is_prime[n-p] 时，n-p 不会是 0, 1, 2。由于我们关注的是奇素数，2 的排除是合理的。

2. solve(n) 函数逻辑

• 特殊情况处理 (n < 8):

  • 如果 n<8，直接返回 -1。
  • 对于 n=2：无法构成，因为 1, 2 的差是 1，不是奇素数。
  • 对于 n=4：例如 1, _, _, _。如果差是 3 (奇素数)，可以是 1,4,_,_。下一个差是 3，4-3=1 (重复) 或 4+3=7 (越界，模 4 为 3)。1,4,3,_。下一个差是 3，3-3=0 (越界，模 4 为 4) 或 3+3=6 (越界，模 4 为 2)。得到 1,4,3,2。差值为：|4-1|=3, |3-4|=1 (非奇素数)。难以构造。
  • 对于 n=6：如果尝试用 p=3, q=n-p=3。构造出的序列可能是 1, 1+3=4, 4+3-6=1, ... 即 1, 4, 1, 4, 1, 4，元素不唯一，不满足 "n个不同整数" 的要求。因此 n=6 也无解。
  • 所以 n < 8 时返回 -1 是合理的。

• 寻找合适的奇素数对 (p, q):

  • 函数遍历预处理好的奇素数列表 primes。
  • 对于每个奇素数 p：
    • 如果 p >= n，那么 n-p <= 0，不可能是另一个素数，所以跳出循环。
    • 检查 is_prime[n-p] 是否为 True。
      • 因为 n 是偶数，p 是奇素数，所以 n-p 必然是奇数。
      • 如果 is_prime[n-p] 为 True，这意味着我们找到了一个奇素数 q = n-p。此时，我们有一对奇素数 (p, q)，它们的和为 n。

• 构造序列 ans:

  • 一旦找到这样的一对 (p, q) (代码中只用到了 p)，就开始构造序列。
  • 序列的第一个元素 ans[0] 初始化为 1。
  • 后续的元素通过 ans.append((ans[-1] + p - 1) % n + 1) 生成。
    • 这个公式可以理解为：当前元素 a_i 是由前一个元素 a_{i-1} 加上 p (在模 n 的意义下) 得到的。具体来说，a_i = ((a_{i-1} - 1 + p) % n) + 1。
    • 这等价于序列 a_k = (k \cdot p \pmod n) + 1 (对于 k = 0, 1, \dots, n-1)。
  • 序列元素的性质：
    1. 差值： 相邻两个元素 a_k 和 a_{k+1} 的差值（考虑环形，即 a_n 与 a_0），其绝对值要么是 p，要么是 n-p (即 q)。由于 p 和 q 都是奇素数，这个条件满足。
    2. 唯一性： 序列 a_k = (k * p % n) + 1 包含 n 个从 1 到 n 的不同整数，当且仅当 gcd(p, n) = 1。
       • 因为 p 是素数，gcd(p, n) = 1 等价于 p 不能整除 n。
       • 如果 p 整除 n，则 n = m * p。如果此时 n-p = (m-1)p 也是素数，那么必然有 m-1=1，即 m=2，所以 n=2p。这种情况下 p = n-p = q。
       • 例如，对于 n=10，会先尝试 p=3，此时 n-p=7 (也是素数)。由于 p=3 不能整除 n=10，所以 gcd(3,10)=1，构造的序列元素是唯一的。

• 返回结果：

  • 如果找到了合适的 p 并成功构造了序列 ans，则将其转换成字符串格式输出。

复杂度分析

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(n)。

总结

该算法的核心是基于哥德巴赫猜想的一个变种：任何一个大于等于6的偶数 n 都可以表示为两个奇素数之和（这里我们还需要这两个素数不同，以保证 gcd(p,n)=1，或者说，当 n=2p 时，我们希望能找到另一对和为 n 的不同奇素数）。代码巧妙地利用了 a_k = (k * p % n) + 1 的构造方式，确保了相邻元素的差的绝对值为 p 或 n-p。

【加强】能否只用3，5，7三个素数构造，如果不行3，5，7，11四个素数呢？

下附只用3，5，7，11四个素数的做法

for i in range(int(input().strip())):
    n = int(input())
    left, right, mid = [], [], []
    a8 = [8, 3, 6, 1, 4, 7, 2, 5]
    a10 = [10, 3, 6, 9, 2, 5, 8, 1, 4, 7]
    a12 = [12, 7, 2, 5, 10, 3, 8, 1, 6, 11, 4, 9]
    a14 = [12, 1, 4, 7, 10, 13, 2, 5, 8, 11, 14, 3, 6, 9]
 
 
    def dfs(n):
        global left, right, mid
 
 
        stack = [n]  # 初始化栈，压入初始的 n
 
        while stack:
            current_n = stack.pop()  # 弹出栈顶的 n
 
            if current_n < 16:
                # 处理基线条件
                if current_n == 8:
                    mid = a8
                elif current_n == 10:
                    mid = a10
                elif current_n == 12:
                    mid = a12
                elif current_n == 14:
                    mid = a14
            else:
                # 处理递归分支
                if (current_n // 8) % 2 == 0:
                    left += [current_n - 2, current_n - 7, current_n - 4, current_n - 1, current_n - 6, current_n - 3]
                    right += [current_n - 5, current_n]
                else:
                    left += [current_n, current_n - 5]
                    right += [current_n - 3, current_n - 6, current_n - 1, current_n - 4, current_n - 7, current_n - 2]
 
                # 将下一个待处理的 n 压入栈（模拟递归调用）
                stack.append(current_n - 8)
 
    if n <= 6:
        print(-1)
    else:
        dfs(n)
        ans = left + mid + right[::-1]
        print(*ans)

【G】K人训练方阵：

题目解读

这道题要求我们计算从 个队员中选出若干队员组成一个【k 人方阵】的方案数。根据题目描述： 一个【k 人方阵】由一名领队和若干排（可以是 0 排）队员组成，每排恰好有 个人。 因此，一个【k 人方阵】的总人数 必须满足 ，其中 是排数。 这个等式意味着方阵的总人数 必须满足两个条件：

1. （至少有领队）
2. （总人数模 余 1）

题目还特别说明，只需要选出能够组成方阵的队员即可，不关心具体谁是领队、谁在哪一排、站在哪个位置。所以，问题转化为： 从 个队员中选出一个子集，要求子集的大小（人数） 满足 且 。计算有多少种选择子集的方法？

结果需要对 取模。

数学建模

从 个队员中选出 个队员的方案数是组合数 。 我们需要计算的是所有满足条件的 对应的 的总和。 即，答案为：

特殊情况分析

Case 1: k = 1

当 时，条件变为 且 。 任何整数 都满足 。所以 这个条件永远无法满足。

但是，我们回顾【k 人方阵】的结构定义：1 个领队 + 排，每排 人。 当 时，每排 1 人。总人数 。由于 ，所以 可以是 。 这意味着，只要选出的人数 ，就可以组成一个【1 人方阵】。 问题就变成了：从 个人中选出至少 1 个人的方案数。 这等价于计算 个人所有子集的数量（），再减去空集（1种）。 所以，当 时，答案是 。 代码中 ans[i] = (pow(2, n, mod) - 1) % mod 正是计算这个值。

Case 2: k = 2

当 时，条件变为 且 。 这意味着选出的人数 必须是正奇数。 我们需要计算： 考虑二项式定理： 令 ，得到 (所有组合数之和) 令 (对于 )，得到 即 (偶数项和等于奇数项和) 因为偶数项和 + 奇数项和 = ，并且两者相等，所以每一部分的和都是 。 我们要求的正是奇数项的和，所以答案是 。（此结论在 时成立。如果 ，答案应为 0，而 是 ，模意义下是 500000004，需要注意 的边界情况，但题目通常 ）。 代码中 ans[i] = pow(2, n - 1, mod) 正是计算这个值。

一般情况 k >= 3：多项式快速幂

对于 ，我们需要计算

这里的 可以转化为多项式 中 的系数，也可以理解成系数 一元多项式环，在多项式剩余类环上进行幂运算。下面是证明过程，如果你对多项式足够了解可以直接跳到最后。

考虑一个动态规划的思路。令 dp[j] 表示从已经考虑过的队员中选出一个子集，使得子集大小模 余 的方案数。 当我们考虑一个新的队员时，对于当前的状态 dp 数组，会产生一个新的状态 dp'：

• 如果不选这个新队员，那么模 余 的方案数仍然是 dp[j]。
• 如果选择这个新队员，那么它会使得原来模 余 (j-1)%k 的子集变成模 余 的子集，这部分贡献的方案数是 dp[(j-1)%k]。 所以状态转移是： dp'[j] = (dp[j] + dp[(j - 1 + k) % k]) % mod。

初始状态（0 个队员）是只有一个空集，大小为 0，所以 dp = [1, 0, 0, ..., 0]（长度为 k）。 考虑 个队员的过程，相当于将这个转移过程执行 次。

这个转移过程可以用多项式乘法来理解。 将状态 dp 数组看作一个多项式的系数：

状态转移 dp'[j] = dp[j] + dp[(j-1+k)%k] 恰好对应于将多项式 乘以 ，然后在模 的意义下进行计算。

在模 下，。 所以 。

的 系数是 ，这与我们的 DP 转移一致。

初始状态是 （对应数组 [1, 0, ..., 0]）。 经过 次转移（考虑 个队员），最终的状态对应的多项式是 。 最终的 dp 数组就是 的系数数组。 dp[j] 表示从 个人中选出子集大小模 余 的方案数。 即 。

我们要求的是 且 的方案数。这正好是最终状态 dp 数组的第 1 项 dp[1]。（因为 时 ，不影响 ）。 所以，我们的目标是计算多项式 中 的系数。

代码采用二进制幂（快速幂） 的方法来计算 。

• base[0] 存储的是 的系数数组 [1, 1, 0, ..., 0]。
• base[j] 存储的是 的系数数组。通过 base[j+1] = base[j] * base[j] 来递推计算。这里的乘法是多项式乘法模 。
• mul(a, b, k) 函数实现了两个多项式（系数数组为 a 和 b）相乘并模 的运算。它计算 res[r] = sum(a[i] * b[j]) 对所有满足 (i + j) % k == r 的 i, j 求和。这是一个 的实现。
• 主循环根据 的二进制表示来累乘。res 初始化为 (系数数组 [1, 0, ..., 0])。如果 的第 位是 1，就将 res 乘以 base[j]。
• 最终 res 数组就是 的系数数组。
• 我们需要的结果是 res[1]。

代码解析

from sys import stdin
input = lambda: stdin.readline().rstrip()
mod = 10**9 + 7

def mul(a, b, k):
    res = [0] * k
    for i in range(k):
        for j in range(k):
            r = (i + j) % k
            res[r] = (res[r] + a[i] * b[j]) % mod
    return res

quests = [[] for _ in range(101)] # 离线询问
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    quests[k].append((n, i))
    
ans = [None] * t
for k in range(1, 101):
    if k == 1:
        for n, i in quests[k]:
            ans[i] = (pow(2, n, mod) - 1) % mod
    elif k == 2:
        for n, i in quests[k]:
            ans[i] = pow(2, n - 1, mod)
    else:
        base = [None] * 24
        base[0] = [1, 1] + [0] * (k - 2)
        for j in range(23):
            base[j + 1] = mul(base[j], base[j], k)
            
        for n, i in quests[k]:
            res = [1] + [0] * (k - 1)
            for j in range(24):
                if (n >> j) & 1:
                    res = mul(res, base[j], k)
            ans[i] = res[1]
            
for x in ans:
    print(x)

代码实现细节

• 离线处理: 代码首先读取所有 个查询，并将它们按 值分组存入 quests 列表。这样做的好处是，对于相同的 ，可以复用预计算的 base 数组。
• 快速幂: 使用二进制幂加速计算 。range(24) 意味着代码假设 。
• 时间复杂度: mul 函数复杂度 。计算 base 数组需要 。处理每个查询需要 。总复杂度大约是 ，