AtCoder Beginner Contest 335
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;
}