## 小 h 学步
#数学 #序列dp
首先我们做个差，每个维度的每个坐标减一下上一个坐标，这样子就变成了相对坐标（相对于上一步）。接下来可以发现 $n$ 和值域很小，只有 $100$，因此先打个暴力试试水。
设 $dp_{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^3Vd)$，加上玄学优化可以直接通过。
不过还可以进一步思考。既然每一维分开计算了那么假设当前这一维选择了 $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\limits_{i\ne j}^n a_ia_j$。对于一个 $a_i$，其它地方有 $n^{n-1}$ 种选项，因此它首先会给答案贡献 $a_i^2\times n^{n-1}$。然后对于后面一坨，它会给答案贡献 $a_i\times\sum\limits_{j\ne i}a_j\times n^{n-2}$，但是由于每一组可以任选（即 $a_j$ 可能是第 $j$ 组中的任意一个），而每一组每个维度的和为 $0$，因此后面那一大坨其实都是 $0$。答案就是 $\mathcal O(\sum\limits_{d}\sum a_{i,j,d}^2\times n^{n-1})$，其中 $a_{i,j}$ 是第 $i$ 组第 $j$ 个的 $d$ 维坐标。
时间复杂度 $\mathcal O(dn^2)$。其实 $100$ 还是太小了，应该把 $n$ 或者 $d$ 扩大到 $1000$，不然太有“疑似暴力”的诱导性了。
```cpp
#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(nm^2)$ 的暴力 dp，说明概率和期望还得再练。最后一题脑子抽风了没有拿到应该拿的十分，有点可惜。至于第三题，实在太难了，还要练。