2025.9.9 模拟赛

小 h 学步

数学 序列dp

首先我们做个差，每个维度的每个坐标减一下上一个坐标，这样子就变成了相对坐标（相对于上一步）。接下来可以发现 $n$ 和值域很小，只有 $100$，因此先打个暴力试试水。

设 $d{p}_{i,j}$ 表示目前走了 $i$ 步，坐标为 $j$，那么下一次就可以选择第 $i+1$ 组中的任意一个坐标加上。时间复杂度 $\mathcal{O}(n^2(nV{)}^d)$，但是由于 $d\le 3$ 因此直接炸裂。

仔细思考，可以发现每个维度是可以拆开来进行计算的。假设 $d=3$ 吗，第 $i$ 步选择了 $(x_i,y_i,z_i)$，那么它会对答案做出 $\sum x_i^2+\sum y_i^2+\sum z_i^2$ 的贡献，拆成三分分别相加。这样动态规划就只用处理一维的问题 $\mathcal{O}(n^{3}Vd)$，加上玄学优化可以直接通过。

不过还可以进一步思考。既然每一维分开计算了那么假设当前这一维选择了 $a_1,a_2,\cdots ,a_n$，那么它会给答案增加 $(a_1+a_2+\cdots +a_n{)}^2$ 的贡献，拆开得到 $a_1^2+a_2^2+\cdots +a_n^2+\sum _{i\ne j}^n{a}_i{a}_j$。对于一个 $a_i$，其它地方有 $n^{n-1}$ 种选项，因此它首先会给答案贡献 $a_i^2\times n^{n-1}$。然后对于后面一坨，它会给答案贡献 $a_i\times \sum _{j\ne i}{a}_j\times n^{n-2}$，但是由于每一组可以任选（即 $a_j$ 可能是第 $j$ 组中的任意一个），而每一组每个维度的和为 $0$，因此后面那一大坨其实都是 $0$。答案就是 $\mathcal{O}(\sum _d\sum a_{i,j,d}^2\times n^{n-1})$，其中 $a_{i,j}$ 是第 $i$ 组第 $j$ 个的 $d$ 维坐标。

时间复杂度 $\mathcal{O}(d{n}^2)$。其实 $100$ 还是太小了，应该把 $n$ 或者 $d$ 扩大到 $1000$，不然太有“疑似暴力”的诱导性了。

#include <iostream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 105, kMod = 998244353;
 
LL n, d, ans;
vector<LL> a[kMaxN][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;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> d;
  for (LL i = 1; i <= n; i++) {
    for (LL j = 1; j < n; j++) {
      a[i][j].resize(d);
      for (LL &k : a[i][j]) {
        cin >> k;
      }
    }
  }
  for (LL i = 1; i <= n; i++) {
    a[i][n] = a[i][n - 1];
    for (LL &j : a[i][n]) {
      j = -j;
    }
    for (LL j = n - 1; j >= 2; j--) {
      for (LL k = 0; k < d; k++) {
        a[i][j][k] -= a[i][j - 1][k];
      }
    }
  }
  for (LL i = 0; i < d; i++) {
    for (LL j = 1; j <= n; j++) {
      for (LL k = 1; k <= n; k++) {
        ans = (ans + a[j][k][i] * a[j][k][i] % kMod * pow(n, n - 1) % kMod) % kMod;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

小球进洞

概率与期望 概率dp 树形dp

我打的暴力。爆搜 $m$ 层挖洞，最后一个 $\mathcal{O}(n)$ 统计。对于一个非叶子节点，如果它的子树边上有 $a$ 个洞，又有 $b$ 个叶子节点，那么它的球就有 $a+b$ 种方式掉进洞里面。由于每个球是独立的，方案数就是它们的乘积。把所有掉洞的方案数加起来再除以挖洞方案数就是答案。时间复杂度 $\mathcal{O}(n^{m}n)$，成功获得 $20$ 分。

快速 kmp

分

不到啊，我没打暴力。

宿舍派对

不到啊，我没打暴力。

其实可以 bfs 暴力。枚举终点，这样子前进就是有方向的了。时间复杂度 $\mathcal{O}(N^2)$，可以获得 $10$ 分。

总结

总分：$100+20+0+0=120$。

第一题还是可以的，找到了公式薄纱了一部分纯暴力的。不过第二题没有想出来 $\mathcal{O}(n{m}^2)$ 的暴力 dp，说明概率和期望还得再练。最后一题脑子抽风了没有拿到应该拿的十分，有点可惜。至于第三题，实在太难了，还要练。