A - 2023 (abc335 A)
题目大意
给定一个字符串，将最后一位改成4。
解题思路
模拟即可。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; s.back() = '4'; cout << s << '\n'; return 0;}B - Tetrahedral Number (abc335 B)
题目大意
给定\(n\)，按字典序输出非负整数\(i,j,k\)，使得 \(i+j+k\leq n\)
解题思路
\(n\)只有 \(21\)，直接 \(O(n^3)\)枚举判断即可。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i <= n; ++i) for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) if (i + j + k <= n) cout << i << ' ' << j << ' ' << k << '\n'; return 0;}C - Loong Tracking (abc335 C)
题目大意
二维网格，贪吃蛇，移动，进行\(q\)次操作，分两种
- 指定贪吃蛇下一步移动的方向
- 指定\(i\)，输出贪吃蛇的第 \(i\)个部位的坐标。
解题思路
每移动一次，只有头部到了新的坐标，其他部分的坐标都变成前一个。
如果我们把每个部分的坐标按顺序放在一个队列里，队尾是头部坐标，队头是尾部坐标，每次移动相当于一次出队和一次入队。
但stl的队列queue不支持随机访问，因此用vector模拟这个队列即可。
出队其实没有必要操作，不断push_back即可。问第\(i\)个部位坐标就从队尾倒着数即可。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector<array<int, 2>> pos(n); for (int i = 0; i < n; ++i) { pos[i] = {n - i, 0}; } map<char, array<int, 2>> dir{ {'U', {0, 1}}, {'D', {0, -1}}, {'L', {-1, 0}}, {'R', {1, 0}}}; while (q--) { int op; cin >> op; if (op == 1) { string s; cin >> s; auto [x, y] = pos.back(); auto [dx, dy] = dir[s[0]]; x += dx; y += dy; pos.push_back({x, y}); } else if (op == 2) { int s; cin >> s; auto [x, y] = *(pos.end() - s); cout << x << ' ' << y << '\n'; } } return 0;}D - Loong and Takahashi (abc335 D)
题目大意
给定一个\(n \times n\)的二维网格，\(n\)奇数，给每个格子一个数字\(\in [1, n^2 - 1]\)，要求每个数字仅使用一次，且相邻数字的格子相邻，且正中间的格子不能是数字，而是T。
给出一种构造方法。
解题思路
按照样例的构造方式，一个螺旋回字构造即可。
每次一个螺旋回字构造就填充最外围的一圈，起点依次为\((1,1) \to (2,2) \to (3,3)\) ，最后恰好到正中间，因此能恰好填满。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; int mid = n / 2; vector<vector<int>> tu(n, vector<int>(n, 0)); int num = 1; array<array<int, 2>, 4> dir{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}}; int cur = 0; int x = 0, y = 0; while (x != mid || y != mid) { tu[x][y] = num; auto [dx, dy] = dir[cur]; int nx = x + dx, ny = y + dy; while (nx < 0 || nx >= n || ny < 0 || ny >= n || tu[nx][ny] != 0) { cur = (cur + 1) % 4; auto [dx, dy] = dir[cur]; nx = x + dx, ny = y + dy; } ++num; x = nx, y = ny; } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (i == mid && j == mid) cout << 'T' << ' '; else cout << tu[i][j] << " \n"[j == n - 1]; } return 0;}E - Non-Decreasing Colorful Path (abc335 E)
题目大意
给定一张无向图，点有点权。
找一条从\(1\to n\)的路径，其点权不递减，且不同的数的个数最多。不存在则输出\(0\)。
解题思路
注意到这个路径要求点权是一个不严格递增的情况，这明显存在一个决策的方向性，即点权大的一定从点权小的求得答案，当点权小的答案都求完了，那么该点权大的答案也求完了，即固定了，知晓了。
因此就直接设\(dp[i]\)表示到达点 \(i\)时的最大的答案（不同的数的个数最多），按照点权从小到大转移，若点权相同则按照答案从大到小转移。用优先队列维护转移顺序即可。往后转移。初始条件为\(dp[1] = 1\)
也可以根据点权构造边权，注意到图如果有环，其边权一定都是\(0\)，缩环后变成一张DAG（有向无环图），直接拓扑 \(DP\)即可，其实跟上面是一样的。
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const int inf = 1e9;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> a(n); for (auto& i : a) cin >> i; vector<vector<array<int, 2>>> edge(n); auto add = [&](int u, int v) { if (a[u] <= a[v]) edge[u].push_back({v, -(a[u] != a[v])}); }; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; --u, --v; add(u, v); add(v, u); } vector<int> dis(n, inf); dis[0] = -1; priority_queue<array<int, 3>> q; q.push({-a[0], -dis[0], 0}); while (!q.empty()) { auto [_, d, u] = q.top(); q.pop(); if (dis[u] != -d) continue; for (auto [v, w] : edge[u]) { if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.push({-a[v], -dis[v], v}); } } } debug(dis); cout << max(0, -dis.back()) << '\n'; return 0;}F - Hop Sugoroku (abc335 F)
题目大意
给定一个\(n\)个数的数组\(a\)， 你在\(0\)处。当你在 \(i\)处时，你可以移动到 \(j = i+a_i \times k < n\)处，\(k\)为正整数，也可以不移动。
问你可以移动到的位置的集合数量。
解题思路
注意到每次移动一定是往右边移动，具有明显的决策方向性，可以设\(dp[i]\)表示移动到第 \(i\)个位置时，移动位置的集合数量（即这个集合中的最大值为 \(i\)的集合数量）。
转移式则为\(dp[i] = \sum_{j \% a_j == i \% a_j} dp[j]\)，初始条件为 \(dp[0] = 1\)。
上述\(dp\)的复杂度为 \(O(n^2)\)，考虑如何优化转移。
但思考下会发现上述转移最坏情况就是 \(O(n)\)，当 \(a_j\)全部为\(1\)时 ，就要对每个\(j\)都累加。但因为是对每个 \(j\)都累加，事实上我们可以预先处理出前缀和，这样就可以 \(O(1)\)。
考虑这个前缀和的形式是怎样的，我们对\(a_j\)的值进行了枚举，假设为 \(x\)，那满足转移条件的 \(j\) 则为\(j \% x == i \% x = y\)，我们要把这些 \(j\)的 \(dp[j]\)累加，即 \(sum[x][y] = \sum_{j \% x == y} dp[j]\) ，这样\(dp[i] = \sum_{x=1}^{\max a}sum[x][i \% x]\)。
但因为\(\max a\)是 \(2e5\)，和\(n\)同一个数量级，上述转移 复杂度还是\(O(n^2)\)。
但注意到如果\(a_j\)比较大时，满足条件的\(j\) 的数量是很少的，这种情况下我们可以暴力转移，这个转移是往后转移，即当前为\(i\)，则 \(dp[j] += dp[i](j = i + a_i \times k)\)。
这期间就有个分界点，我们设分界点为\(mid = \sqrt{n}\)
- 当\(a_i > mid\)时，我们暴力更新后面的\(dp[j]\)，这样的\(j\)的数量（即 \(k\)的数量）不超过\(\frac{n}{\sqrt{n}} = \sqrt{n}\)个。更新的复杂度是\(O(n \sqrt{n})\)
- 当\(a_i \leq mid\)时，由于转移的数量 \(j\)很多，我们就先不转移，先保存在 \(sum\)数组里（可以看成是懒标记），即 \(sum[a_i][i \% a_i] += dp[i]\)。更新的复杂度是\(O(1)\)
这样，对于后续的一个\(i\)的 \(dp[i]\)的值，注意到原始转移式是\(dp[i] = \sum_{j \% a_j == i \% a_j} dp[j]\)，我们已经把情况一（即\(a_j > mid\)）的\(dp[j]\)累加进 \(dp[i]\)里了，还剩下\(a_j \leq mid\)的没累加进来，因此此时再 \(dp[i] += \sum_{j = 1}^{mid}sum[j][i \% j]\)即可。更新的复杂度是\(O(n \sqrt{n})\)
最终的时间复杂度是\(O(n\sqrt{n})\)。
注意到上述转移里，我们把\(j\)和 \(a_j\)是割裂开了，考虑 \(a_j\)的所有取值情况，然后分成两类分别处理。
这其实也是一类经典的\(dp\)优化方法，即根号分治\(dp\)，即存在两种形式的转移，且在不同数量级下时间复杂度各有优势，然后结合起来， \(\sqrt{n}\)是一个经典的分界点
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;const int mo = 998244353;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; int half = sqrt(n); vector<vector<int>> sum(half, vector<int>(half, 0)); vector<int> a(n); for (auto& i : a) cin >> i; vector<int> dp(n); dp[0] = 1; for (int i = 0; i < n; ++i) { for (int j = 1; j < half; ++j) { dp[i] += sum[j][i % j]; if (dp[i] >= mo) dp[i] -= mo; } if (a[i] >= half) { for (int j = i + a[i]; j < n; j += a[i]) { dp[j] += dp[i]; if (dp[j] >= mo) dp[j] -= mo; } } else { sum[a[i]][i % a[i]] += dp[i]; if (sum[a[i]][i % a[i]] >= mo) sum[a[i]][i % a[i]] -= mo; } } int ans = 0; for (auto& i : dp) { ans += i; if (ans >= mo) ans -= mo; } cout << ans << '\n'; return 0;}G - Discrete Logarithm Problems (abc335 G)
题目大意
给定一个数组\(a\)和一个质数\(P\)，求 \((i,j)\)的数量，满足以下条件
- 存在 \(k\)，使得 \(a_i ^ k \equiv a_j (\mod P)\)
解题思路
这题难在需要有数论知识。
首先因为有质数\(P\)，会存在一个原根 \(g\)，使得 \(g^0 \sim g^{P-2}\)的值恰好取遍了 \(1 \sim P-1\) ，由费马小定理知\(g^{P-1} \equiv g^0 \equiv 1(\mod P)\)就回到了起点。上述的幂是对\(P\)取模的。
因此\(a_i\)可以找到个 \(x\)，使得 \(g^x \equiv a_i (\mod P)\)，对应的\(a_j\)则对应\(y\)。
除此之外，关于阶的概念：一个数的阶是一个最小的正整数\(m\)，使得 \(a_i ^ m \equiv 1 (\mod P)\) ，其实就是循环节的长度，一般记为\(ord(a_i)\)。
然后是一个简单但深刻的定理：
- 如果存在\(k\)，使得\(a_i^k \equiv a_j(\mod P)\)，则有 \(ord(a_j) | ord(a_i)\)
如何通俗点理解呢？考虑阶的定义，\(g^{xm} \equiv 1 \equiv g^0(\mod P)\)，关心指数部分的话，即为 \(xm \equiv 0 (\mod P-1)\) ，即\(xm = n(P-1)\)。
注意到\(m\)是最小的，怎么最小呢？我们要让 \(xm\)是 \(P-1\)的倍数，我们将 \(x\)和 \(P-1\)质因数分解， \(x\)缺少的那些质因数就是造成\(x\)不是 \(P-1\)的倍数的原因，这缺少的部分就由 \(m\)补上，那这个 \(m\)就是最小的了。注意这里的\(m\)就是一个数的阶\(order\)。它就是 \(x\)相对于 \(P-1\)缺少的那部分质因数，所以也必定是 \(P-1\)的因子
这里得到了另一个简单但也深刻的定理，也是最后求一个数的阶的理论依据：
- \(ord(a_i) | P-1\)
对于 \(a_j\)来说，就是 \(ym^{\prime}=kxm^{\prime} = n^{\prime}(P-1)\)。我们知道\(xm\)已经是 \(P-1\)的倍数了，那 \(kxm\)也必定是 \(P-1\)的倍数，但这里的\(m\)不一定是最小的，因为 \(k\)也带来了一些 \(P-1\)的质因数，因此 \(m^\prime\)会比 \(m\)更小，它去掉了 \(k\)包括的 \(P-1\)的一些质因数，也即 \(m^{\prime} | m\)，即\(ord(a_j) | ord(a_i)\)。
因此，如果我们求出了每个\(a_i\)的阶，剩下的就是求一个数的倍数有多少个。
如何快速求一个数的阶呢？注意到 \(ord(a_i) | P-1\)，我们先假设其阶\(m=P-1\)，此时必有 \(a_i^{P-1} \equiv 1(\mod P)\)，但此时可能不是最小的，因为关于 \(P-1\)的质因数有多余的（跟上面的 \(kxm\)的 \(m\)不是最小的一个道理），我们要把多余的质因数去掉。
如何去除呢？其实只要枚举去除哪个质数，去除该质数的指数是多少即可。当去除的过多时，就不满足\(a_i^{m} \equiv 1(\mod P)\) ，但还能去除时，则还会满足该等式。所谓最小的\(m\)，意味着任何一个更小的数，都不会满足该等式。
注意到 \(P\)只有 \(1e13\)，质因数种类最多只有 \(\log P\)个，每个质数的幂最大也只有 \(\log P\) ，因此可以在\(O(\log^3 P)\)的复杂度内求出一个数的阶（还有一个\(\log\)是快速幂）。
因此一开始先对\(P-1\)质因数分解，然后求出每个数的阶，此时显然不能\(O(n^2)\)枚举阶，判断倍数关系。
注意到 \(P-1\)只有\(10^{13}\)，最多只有 \(12\)个左右的质数，因此其因数个数最多只有 \(2^12\)，是\(d=O(10^3)\)的数量级，因为阶一定是\(P-1\)的倍数，虽然有 \(O(n)\)个，但不同的阶的数量不超过 \(O(d)\)，因此我们可以统计每个阶的数量，直接 \(O(d^2)\)枚举每个阶的数量，判断倍数累加答案即可。
注意判阶数时的快速幂可能会爆long long。
最终的时间复杂度是\(O(n\log^3 P) + d^2(P-1))\)
神奇的代码
#include <bits/stdc++.h>using namespace std;using LL = long long;long long qpower(__int128 a, __int128 b, long long mo) { __int128 qwq = 1; while (b) { if (b & 1) qwq = qwq * a % mo; a = a * a % mo; b >>= 1; } return qwq;}int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; LL mo; cin >> n >> mo; LL phi = mo - 1, tmp = phi; vector<LL> a(n); for (auto& i : a) cin >> i; vector<LL> prime; int half = sqrt(phi) + 1; for (int i = 2; i <= half; ++i) { if (phi % i == 0) { prime.push_back(i); while (phi % i == 0) phi /= i; } } if (phi != 1) prime.push_back(phi); phi = tmp; map<LL, int> cnt; auto order = [&](LL x) { LL m = phi; for (auto& i : prime) { while (m % i == 0 && qpower(x, m / i, mo) == 1) { m /= i; } } return m; }; for (auto& i : a) { cnt[order(i)]++; } LL ans = 0; for (auto& i : cnt) { for (auto& j : cnt) { if (i.first % j.first == 0) { ans += 1LL * i.second * j.second; } } } cout << ans << '\n'; return 0;}