2025.9.4 模拟赛

剖分

树形dp 前缀和 后缀和 乘法逆元

首先我第一眼就看出了这是一道树形 dp 计数题，于是就设了状态：$d{p}_i$ 表示在 $i$ 子树内有多少种符合要求的方案。但是这个无法转移，原因是状态太过于简单了。我们在树上选择的路径有两种，一种是其中一个端点是另外一个端点的祖先（称作简单路径），另外一种是端点的 LCA 是独立出来不同于两个端点的（称作复杂路径）。

于是我就设计了一个新的状态。$d{p}_{i,0/1}$ 表示在 $i$ 子树中，$i$ 在它所在的路径中是 LCA 还是端点。如果是要让 $i$ 作为 LCA，那么就需要枚举另外两个子节点 $j,k$ 作为端点，拼在 $i$ 的下面构成一个复杂路径，另外的地方随便选；如果要让 $i$ 作为端点，那么就枚举其中一个子节点 $j$ 作为端点，拼在 $i$ 的下面，其它子节点都要作为 LCA（保证一定不会产生意料之外的路径）。

然后就会发现 WA 了。问题是，首先让 $i$ 作为端点，枚举了 $j$ 之后其它节点都只能选择作为 LCA 了吗？其实如果 $i$ 被拼到了它的父亲下面，那么 $j$ 其它的节点是可以任选的，都不会产生意料之外的路径。而如果让 $i$ 作为 LCA 的话，那么除了 $j,k$ 另外的地方并非是可以随便选的，必须要保证不会产生意料之外的路径。

因此我的状态仍然是不够完善的，需要额外增加一条是否会产生意料之外的路径。于是我设计了新的状态 $d{p}_{i,0/1/2}$，$0$ 表示将 $i$ 作为 LCA 的方案数，$1$ 表示将 $i$ 作为简单路径端点、但是如果 $i$ 没有被拼到上方可能导致新路径的方案数，$2$ 表示将 $i$ 作为简单路径端点、无论是否拼上去都不会导致新路径的方案数。注意这里可能导致新路径的方案数是不拼上去一定会导致新路径和一定不会导致新路径的方案数之和。

于是转移就变得简单了。如果作为 LCA 的话，选择两个儿子拼上来，其它地方可以选作为 LCA 或者作为端点但不拼上来不会导致新路径，即

$$d{p}_{x,0}=\frac{1}{2}\sum _{i}d{p}_{i,1}\times \sum _{i\ne j}d{p}_{k,1}\prod _{k\ne i,j}(d{p}_{k,0}+d{p}_{k,2})$$

如果作为端点、不被拼到上方可能导致新路径的话，那么可以选择任意一个儿子拼上来（儿子作为端点无论是否拼上去都不会导致新路径），然后其它任放哪个选作为 LCA 或者作为端点但不拼上去不会导致新路径

$$d{p}_{x,1}=\sum _{i}d{p}_{i,1}\times \prod _{i\ne j}(d{p}_{j,0}+d{p}_{j,2})$$

如果作为端点、不会导致新路径的话，那么可以选择任意一个作为端点无论是否被拼上去都不会导致新路径的儿子，然后其它地方就只能选作为 LCA 了

$$d{p}_{x,2}=\sum _{i}d{p}_{i,1}\times \prod _{i\ne j}d{p}_{j,0}$$

最后是一个额外的特判，就是把 $x$ 独立出来，然后底下就必须全部选择作为 LCA。这个很好处理。以下是我的赛时代码：

#include <iostream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5, kMod = 1e9 + 7;
 
// 复杂路径：端点不是对方的祖先，有和端点不同的 LCA
// 可能导致新路径：包含会导致和不会导致的所有情况
 
LL dp[kMaxN][3], n;
vector<LL> e[kMaxN];
 
LL pow(LL a, LL b) {
  LL res = 1;
  for (; b; b /= 2) {
    b % 2 && (res = res * a % kMod);
    a = a * a % kMod;
  }
  return res;
}
 
LL inv2 = pow(2, kMod - 2);
 
void dfs(LL x, LL f) {
  LL cnt = 0;
  for (LL i : e[x]) {
    if (i != f) {
      dfs(i, x);
      cnt++;
    } 
  }
  if (!cnt) {
    dp[x][1] = dp[x][2] = 1;
    return;
  }
  // 作为一条复杂路径的LCA，选择i->x->j作为新路径，其余地方只能选LCA或者不接不能导致新路径的
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    for (LL j : e[x]) {
      if (j == f || j == i) {
        continue;
      }
      LL sum = 1;
      for (LL k : e[x]) {
        if (k == f || k == i || k == j) {
          continue;
        }
        sum = (sum * (dp[k][0] + dp[k][2])) % kMod;
      }
      dp[x][0] = (dp[x][0] + dp[i][1] * dp[j][1] % kMod * sum % kMod) % kMod;
    }
  }
  dp[x][0] = dp[x][0] * inv2 % kMod;
  // 作为简单路径的头，上面不接可能导致新路径
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    LL sum = 1;
    for (LL j : e[x]) {
      if (j == f || j == i) {
        continue;
      }
      sum = (sum * (dp[j][0] + dp[j][2])) % kMod;
    }
    dp[x][1] = (dp[x][1] + dp[i][1] * sum % kMod) % kMod;
  }
  // 作为简单路径的头，上面不接不会导致新路径
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    LL sum = 1;
    for (LL j : e[x]) {
      if (j == f || j == i)  {
        continue;
      }
      sum = (sum * dp[j][0]) % kMod;
    }
    dp[x][2] = (dp[x][2] + dp[i][1] * sum % kMod) % kMod;
  }
  // 把自己独立出来，但是下面必须都是 LCA 的，这种情况上面接不接都不会导致新路径
  LL sum = 1;
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    sum = (sum * dp[i][0]) % kMod;
  }
  dp[x][1] = (dp[x][1] + sum) % kMod;
  dp[x][2] = (dp[x][2] + sum) % kMod;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1, 0);
  cout << (dp[1][0] + dp[1][2]) % kMod << '\n';
  return 0;
}

不难发现时间复杂度为 $\mathcal{O}\left(\sum _{i=1}^n|so{n}_i|\right)$，如果塞一个菊花图的数据那就直接爆炸了，理论上可以通过所有点度数都不超过 $3$ 的数据，但是由于代码源神的数据太水直接就 AC 了。

但是我们可以使用前后缀优化转移部分来使这个算法时间复杂度变为严格的 $\mathcal{O}(n)$。

首先为了方便，定义一些简写：

$$\{\begin{array}{l}{A}_i=d{p}_{i,1}\\ B_i=d{p}_{i,0}+d{p}_{i,2}\\ C_i=d{p}_{i,0}\end{array}$$

首先是对 $d{p}_{x,0}$ 的转移

$$d{p}_{x,0}=\frac{1}{2}\sum _i{A}_i\times \sum _{i\ne j}{A}_j\prod _{k\ne i,j}{B}_k$$

$i$ 是可以枚举的，因此我们需要计算 $\sum _{i\ne j}{A}_j\prod _{k\ne i,j}{B}_k$，这个可以通过前/后缀和/积来解决。先求出 $B_k$ 的前后缀积，然后考虑前缀每次如果新加入一个 $k$，那么所有老的 $A_j$ 都能多乘上一个新的 $B_k$，而新的 $A_k$ 可以和之前所有的 $B$ 来相乘（看上面的公式）。也就是说如果令 $p_i=\prod _{j=1}^i{B}_j$ 的话，那么可以递推计算 $p_i^{\prime }=(p_{i-1}^{\prime }\times B_i+p_{i-1}\times A_i)$，这里计算的 $p_i^{\prime }$ 实际上等于 $\sum _{j=1}^i{A}_j\prod _{k\in [1,i]\wedge j\ne k}{B}_k$。后缀同理，最后我们只需要用前缀 $p^{\prime }$ 乘上后缀 $p$，再用后缀 $p^{\prime }$ 乘上前缀 $p$，加起来就可以获得 $\sum _{i\ne j}{A}_j\prod _{k\ne i,j}{B}_k$ 了。

至于 $d{p}_{x,1}$ 和 $d{p}_{x,2}$ 转移比较简单。

#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5, kMod = 1e9 + 7, inv2 = 500000004;
 
LL dp[kMaxN][3], n;
vector<LL> e[kMaxN];
 
void dfs(LL x, LL f) {
  vector<LL> son;
  for (LL i : e[x]) {
    if (i != f) {
      dfs(i, x);
      son.emplace_back(i);
    }
  }
  if (son.empty()) {
    dp[x][1] = dp[x][2] = 1;
    return;
  }
  LL m = son.size();
  vector<LL> a(m), b(m), c(m), preprdb(m + 1, 1), sufprdb(m + 1, 1), preprdc(m + 1, 1), sufprdc(m + 1, 1), presumb(m + 1), sufsumb(m + 1), presumc(m + 1), sufsumc(m + 1);
  for (LL i = 0; i < m; i++) {
    LL y = son[i];
    a[i] = dp[y][1];
    b[i] = (dp[y][0] + dp[y][2]) % kMod;
    c[i] = dp[y][0];
  }
  for (LL i = 0; i < m; i++) {
    preprdb[i + 1] = preprdb[i] * b[i] % kMod;
    preprdc[i + 1] = preprdc[i] * c[i] % kMod;
  }
  for (LL i = m - 1; i >= 0; i--) {
    sufprdb[i] = sufprdb[i + 1] * b[i] % kMod;
    sufprdc[i] = sufprdc[i + 1] * c[i] % kMod;
  }
  for (LL i = 0; i < m; i++) {
    presumb[i + 1] = (presumb[i] * b[i] + a[i] * preprdb[i]) % kMod;
    presumc[i + 1] = (presumc[i] * c[i] + a[i] * preprdc[i]) % kMod;
  }
  for (LL i = m - 1; i >= 0; i--) {
    sufsumb[i] = (sufsumb[i + 1] * b[i] + a[i] * sufprdb[i + 1]) % kMod;
    sufsumc[i] = (sufsumc[i + 1] * c[i] + a[i] * sufprdc[i + 1]) % kMod;
  }
  LL sum = 0;
  for (LL i = 0; i < m; i++) {
    sum = (sum + a[i] * ((sufprdb[i + 1] * presumb[i] + preprdb[i] * sufsumb[i + 1]) % kMod) % kMod) % kMod;
  }
  dp[x][0] = (sum * inv2) % kMod;
  dp[x][1] = (presumb[m] + preprdc[m]) % kMod;
  dp[x][2] = (presumc[m] + preprdc[m]) % kMod;
}
 
int main() {
  cin >> n;
  for (LL i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  dfs(1, 0);
  cout << (dp[1][0] + dp[1][2]) % kMod << '\n';
  return 0;
}

取模

数学

我写的暴力。首先如果在没有模 $m$ 的情况下就已经是答案了那就肯定有无数个解，因为当 $m$ 达到比所有数都要大的时候，这时候 $f(m)$ 的值是不变的，如果这时候 $f(m)$ 不是最大值那么 $m$ 就有有限个，否则是无线个。接着我就写了一个 $\mathcal{O}(nV)$ 的暴力。

金币

背包dp 单调队列

我只看到了 $n=0$ 的数据因此只是全部加起来之后再乘上 $t$ 输出。主要是没有注意到题目中如果买了新的金币卡，那么原来的金币卡就会失效，导致我思考得过于复杂了。

画图

启发式合并 并查集

首先这题目要用动态数组存矩阵。我只交了暴力，就是 dfs 搜连通块然后染色。$R=1$ 的数据我想到了使用 set 存储相同颜色段，但是只有十分钟了实现失败。

总结

总分：$100+20+5+10=135$。

首先是第一道题目，我设计的状态错误了两次，导致了大量时间浪费在调试上面（而且是无意义的调试），最后也没有想到如何去优化转移为严格 $\mathcal{O}(n)$，只是数据太水过了，很容易被卡。然后是第二题，我没有想到 $\mathcal{O}(n\sqrt{V})$ 的算法，说明整除取模这一块还得练。然后第三题因为题目信息没获取完全导致我思考得过于复杂错失了完全背包的解法。最后是最后一题因为我调试时间太长了导致没时间写 $R=1$ 的数据。总的来说就是状态设错、调试太长、不会优化转移、不会整除，下次遇到像第一题这样要想清楚状态了再写，并在写的过程中时刻想着如何转移、如何优化。