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;
}



热门相关:布衣官道   暖君   布衣官道   恶明   恶明