Rank 114/3990. Solved 10/13.

罚时爆炸场

A. 智乃与瞩目狸猫、幸运水母、月宫龙虾

题意

给定两个字符串 \(s, t\)，判断他们的首字母在不区分大小写的情况下是否相等。

思路

如题。可以使用 \(\mathtt{toupper}\) 之类的函数。

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    string s, t;
    cin >> s >> t;
    if(toupper(s[0]) == toupper(t[0])) cout << "YES\n";
    else cout << "NO\n";
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

手速

B. 智乃的数字手串

题意

给定一个长为 \(n\) 的头尾相连的数组 \(a\)，定义操作为：

1. 取数：找出两个相邻数，满足和为偶数，并删除任意一个数；

2. 交换：交换任意两个数

对于 \(A, B\) 之间的博弈，每轮每个玩家一定需要进行取数操作，而交换操作可选，若某个玩家无法取数，那么判定该玩家输。

当数组中只有一个元素，也可以直接取走。

输出最后的获胜者。

思路

我们可以发现，当一个玩家无法取数时，要么序列中没有数字，要么满足下面的格式：\(\{\) 奇，偶，奇，偶，\(\ldots\)，奇，偶 \(\}\)，或者更具体地说：奇偶交替，且头尾的奇偶性不相同。

那么，显然最后的序列的长度是一个偶数。

而我们可以发现，每次每个玩家只能取走一个数，从而可以得出：偶数为必败态。

从而我们只需关注一开始序列长度的奇偶性，如果长度为奇数，那么先手胜，否则后手胜。

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    cout << (n % 2 == 0 ? "zn\n" : "qcjj\n");
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

乱猜就完事了！

C. 智乃的前缀、后缀、回文

题意

给定一个长为 \(n\) 的字符串 \(s\)，以及一个长为 \(m\) 的字符串 \(t\)。

记 \(pre_{p, x}\) 为字符串 \(p\) 的前 \(x\) 个字符组成的子串，\(suf_{p, x}\) 为字符串 \(p\) 的后 \(x\) 个字符组成的子串。

现在，在 \(s, t\) 中选取 \(pre_s, pre_t, suf_s, suf_t\)，满足 \(pre_s = suf_t, pre_t = suf_s\)，且四个字符串都是回文串。

其中，\(pre_s\) 和 \(suf_s\) 不能出现重叠，\(pre_t\) 和 \(suf_t\) 也不能出现重叠。

输出 \(4\) 个字符串的长度的最大值。

思路

好心的出题人没有卡掉字符串哈希和自然溢出，我们这里考虑用前缀哈希。

我们需要处理几个事情：

1. 简化 \(pre= suf\)，我们可以随便把一个字符串翻转，从而我们只需找出相同的最长回文前缀和最长回文后缀；

2. 如何判断回文，这个用字符串哈希即可。我们可以再预处理出反向的哈希，然后判断对应位置即可；

3. 如何避免重叠，我们可以用老套路，递推处理出 第 \(i\) 个数及以前 中满足条件的最长前缀 \(P_i\)，以及 第 \(i\) 个数及以后 中满足条件的最长后缀 \(S_i\)，然后枚举 \(i \in [1, n - 1]\)，统计 \(P_i + S_{i + 1}\) 的最大值即可。注意这里需要判断前后缀是否都存在，即长度是否都是正数，否则不应计入答案。 当然，为了方便判断，不妨用长度短的字符串作为参考，只要短的字符串没用重叠，长的自然也不会重叠。

如上，套上字符串哈希的板子即可。

时间复杂度：\(O((n + m) \log (n + m))\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

constexpr unsigned int P = 1331;

void solve() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    if(n > m) swap(n, m), swap(s, t);
    reverse(all(t));
    string rs(s), rt(t);
    reverse(all(rs)), reverse(all(rt));
    s = " " + s, t = " " + t;
    rs = " " + rs, rt = " " + rt;
    vector<unsigned int> hs(n + 1), ht(m + 1), hrs(n + 1), hrt(m + 1);
    vector<unsigned int> p(max(n, m) + 1);
    p[0] = 1;
    for(int i=1;i<=max(n,m);i++) p[i] = p[i - 1] * P;
    for(int i=1;i<=n;i++) {
        hs[i] = hs[i - 1] * P + s[i];
        hrs[i] = hrs[i - 1] * P + rs[i];
    }
    for(int i=1;i<=m;i++) {
        ht[i] = ht[i - 1] * P + t[i];
        hrt[i] = hrt[i - 1] * P + rt[i];
    }
    auto palin = [&](int l, int r) -> bool {
        return hs[r] - hs[l - 1] * p[r - l + 1] == hrs[n - l + 1] - hrs[n - r] * p[r - l + 1];
    };
    vector<int> pre(n + 1), suf(n + 2);
    bool f = true;
    for(int i=1;i<=n;i++) {
        if(s[i] != t[i]) f = false;
        pre[i] = pre[i - 1];
        if(f) {
            if(palin(1, i)) pre[i] = i;
        }
    }
    f = true;
    for(int i=n;i>=1;i--) {
        if(s[i] != t[m - (n - i + 1) + 1]) f = false;
        suf[i] = suf[i + 1];
        if(f) {
            if(palin(i, n)) suf[i] = n - i + 1;
        }
    }
    int ans = 0;
    for(int i=1;i<n;i++) {
        if(pre[i] > 0 && suf[i + 1] > 0){
            ans = max(ans, pre[i] + suf[i + 1]);
        }
    }
    if(ans == 0) cout << -1 << '\n';
    else cout << ans * 2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

不卡哈希可还行（不过用哈希写起来也是怪累的

D. chino's bubble sort and maximum subarray sum(easy version)

题意

给定一个数组 \(a\)，定义一次操作为选择两个相邻数，并将其交换。

输出在最多进行 \(K\) 次交换的条件下，最终数组的最大子段和的最大值。

本题中，\(0 \leq K \leq 1\)。

思路

既然 \(K\) 最多只有 \(1\)，那么当 \(K = 1\) 的时候，我们直接暴力枚举要交换的两个元素，并计算答案即可。

至于如何计算答案，最大子段和是一类很经典的 \(dp\)，此处不再赘述。

时间复杂度：\(O(n^2)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    auto how = [&]() -> int {
        vector<int> dp(n + 1);
        int mx = -inf;
        for(int i=1;i<=n;i++){
            if(dp[i - 1] > 0){
                dp[i] = dp[i - 1] + a[i];
            }else{
                dp[i] = a[i];
            }
            if(dp[i] > mx) mx = dp[i];
        }
        return mx;
    };
    int ans = how();
    if(k == 1) for(int i=2;i<=n;i++) {
        swap(a[i], a[i - 1]);
        ans = max(ans, how());
        swap(a[i], a[i - 1]);
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

别爆 \(int\) 了（

E. chino's bubble sort and maximum subarray sum(hard version)

待补充

F. chino's bubble sort and maximum subarray sum(very hard version)

待补充

G. 智乃的比较函数(easy version)

因本人写的有点头大，故没有单独写 \(easy\) 的代码，详见 \(H\)。

H. 智乃的比较函数(normal version)

题意

给定 \(N\) 个三元组 \(<x, y, z>\)，若 \(z = 0\)，则代表 \(x \geq y\)；若 \(z = 1\)，则代表 \(x < y\)。

判断是否存在冲突。

思路

本题的数据范围很小，我们不妨考虑用传递闭包，或者说 \(floyd\)。

具体来说，我们定义两个二维矩阵 \(P, Q\)，其中 \(P[i][j] = 1\) 时代表关系上 \(i<j\)；\(Q[i][j] = 1\) 时代表关系上 \(i \geq j\)。

然后，我们将输入按 \(z\) 分成两部分，分别对 \(P, Q\) 赋值，然后跑一下 \(floyd\) 即可。

最后，冲突的条件为 \(P[i][j] = 1, P[j][i] = 1\)，或者 \(P[i][j] = 1, Q[i][j] = 1\)。

时间复杂度：\(O(n^3)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e1(4, vector<int>(4)), e2(4, vector<int>(4));
    while(n --) {
        int x, y, z;
        cin >> x >> y >> z;
        if(z == 0) e2[x][y] = 1;
        else e1[x][y] = 1;
    }
    for(int i=1;i<=3;i++) {
        for(int j=1;j<=3;j++) {
            for(int k=1;k<=3;k++) {
                if(e1[i][k] == 1 && e1[k][j] == 1) e1[i][j] = 1;
                if(e2[i][k] == 1 && e2[k][j] == 1) e2[i][j] = 1;
            }
        }
    }
    for(int i=1;i<=3;i++) {
        for(int j=1;j<=3;j++) {
            if((e1[i][j] == 1 && e1[j][i] == 1) || (e1[i][j] == 1 && e2[i][j] == 1)) {
                cout << "No\n";
                return;
            }
        }
    }
    cout << "Yes\n";
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

《论这么简单我写了两个小时还挂了 \(6\) 发这件事》

I. chino's infinite infinite strings without xyz

待补充

J. 智乃的相亲活动

题意

对于 \(n\) 个男生和 \(m\) 个女生，给定 \(k\) 对双向的好感关系。

输出包含两部分，第一部分为每个女生根据好感关系，等概率选择一个男生，最后男生数量的期望；第二部分第一部分为每个男生根据好感关系，等概率选择一个女生，最后女生数量的期望。

思路

首先，期望具有相加性，即 \(\text{E}(X + Y) = \text{E}(X) + \text{E}(Y)\)，从而我们可以把问题拆分为每个男生，以及每个女生是否被选中的期望。

因为单个人数量为 \(1\)，从而我们可以直接把期望考虑为概率。

那么现在问题变成了：求每个人被选中的概率。

正着做有点麻烦，我们不妨考虑倒着做，也就是求每个人不被选中的概率。

不被选中的概率可以直接乘起来，也就是说，如果男生 \(A_1\) 选择女生 \(B_1\) 的概率为 \(p_1\)，男生 \(A_2\) 选择女生 \(B_1\) 的概率为 \(p_2\)，那么 \(B_1\) 不被选中的概率就是 \((1 - p_1)(1 - p_2)\)。

如上，我们对男生和女生分别累加概率，然后用各自的人数减掉即为我们需要的期望。

另外，这题可以选择是否输出模意义下的值，但是输出小数着实有点精度问题。

时间复杂度：\(O(n + m)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

static __int128 qp(__int128 x, __int128 y, const __int128 m = mod) {
    static __int128 ans;
    ans = 1, x %= m;
    for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
    return ans;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n + 1), b(m + 1);
    while(k --) {
        int u, v;
        cin >> u >> v;
        a[u].pb(v), b[v].pb(u);
    }
    vector<int> ap(n + 1, 1), bp(m + 1, 1);
    for(int i=1;i<=n;i++) {
        for(auto x : a[i]) bp[x] = bp[x] * ((1 - inv(a[i].size() + mod)) % mod) % mod;
    }
    for(int i=1;i<=m;i++) {
        for(auto x : b[i]) ap[x] = ap[x] * ((1 - inv(b[i].size() + mod)) % mod) % mod;
    }
    int ans1 = 0, ans2 = 0;
    for(int i=1;i<=n;i++) ans1 = (ans1 + ap[i]) % mod;
    for(int i=1;i<=m;i++) ans2 = (ans2 + bp[i]) % mod;
    cout << "modint\n";
    cout << ((n - ans1 + mod) % mod) << ' ' << ((m - ans2 + mod) % mod) << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

差点把正着推的概率全都加起来了（

K. 智乃的“黑红树”

题意

定义 "黑红树" 为一颗二叉树，且每个结点要么不包含子结点，要么包含 \(2\) 个子结点；树的奇数层结点为黑色，偶数层结点为红色。

给定黑色结点和红色结点的个数 \(a, b\)，构造一棵 "黑红树"。

思路

我们肯定是尽可能让 个数最少的颜色 的点固定后，个数最多的颜色 的选择尽可能多，从而避免无解。

下面给出一种构造方案：

1. 一开始，除了叶节点，只有左儿子有两个子结点，且层数等于 \(\min(a, b)\)；

2. 补全即可。

当然在构造前，我们可以先判断 \(a, b\) 的奇偶性，因为显然 \(a\) 为奇数，\(b\) 为偶数。

可以证明的是，构造完后，如果不够补全，就是无解。

时间复杂度：\(O(a + b)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int a, b;
    cin >> a >> b;
    if(a % 2 == 0 || b % 2 == 1) {
        cout << "No\n";
        return;
    }
    vector<int> tp(a + b + 1, -1);
    vector<pii> ans(a + b + 1, {-1, -1});
    int now = 0, ind = 1;
    tp[1] = 0;
    int st = min(a,b), sum = a + b;
    a --;
    for(int i=1;i<st;i++) {
        ans[max(1ll, now)] = {ind + 1, ind + 2};
        now += 2, ind += 2;
        tp[ind - 1] = tp[ind] = i % 2;
        if(i % 2 == 0) a -= 2;
        else b -= 2;
    }
    if(a > 0) {
        for(int i=1;i<=sum;i++) {
            if(tp[i] == 1 && ans[i].fs == -1 && a > 0) {
                ans[i] = { ind + 1, ind + 2};
                ind += 2;
                a -= 2;
            }
        }
        if(a > 0) {
            cout << "No\n";
            return;
        }
    } else {
        for(int i=1;i<=sum;i++) {
            if(tp[i] == 0 && ans[i].fs == -1 && b > 0) {
                ans[i] = { ind + 1, ind + 2};
                ind += 2;
                b -= 2;
            }
        }
        if(b > 0) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
    for(int i=1;i<=sum;i++) cout << ans[i].fs << ' ' << ans[i].sc << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

也是没想到可以 \(\mathtt{bfs}\)（

L. 智乃的36倍数(easy version)

题意

给定一个长为 \(n\) 的数组 \(a\)，取 \(i, j\)，\(i \neq j\)，将 \(a_i\) 和 \(a_j\) 拼接在一起，得到新数字 \(x\)。

输出为 \(36\) 倍数的 \(x\) 的个数。

本题数据范围很小。

思路

本题可以直接暴力枚举，我们不妨读入字符串，拼接字符串后，使用 \(\mathtt{stoi}\) 函数，然后判断是否能被 \(36\) 整除即可。

时间复杂度：\(O(2n^2)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<string> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    int ans = 0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i == j) continue;
            string ok = a[i] + a[j];
            if(stoi(ok) % 36 == 0) {
                ans ++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
//     cin >> t;
    while (t--) solve();
}

手速 *2

M. 智乃的36倍数(normal version)

题意

给定一个长为 \(n\) 的数组 \(a\)，取 \(i, j\)，\(i \neq j\)，将 \(a_i\) 和 \(a_j\) 拼接在一起，得到新数字 \(x\)。

输出为 \(36\) 倍数的 \(x\) 的个数。

本题数据范围相对较大。

思路

考虑到不能直接暴力，我们从整除入手，即：

\(x \equiv a_i \times 10^{Len(a_j)} + a_j \equiv 0 \pmod {36}\)。

因为数字的长度都很小，我们不妨记 \(mp_{m, l}\) 为乘上 \(10^l\) 后在模 \(36\) 意义下和 \(m\) 同余的元素数量。

那么，我们先枚举一遍，统计 \(mp\)，然后再枚举一遍，记 \(a_i \equiv t \pmod {36}\)，那么对应另一半的值就是 \(36 - t \pmod {36}\)。

我们将 \(a_i\) 作为被拼接的右边的数，那么需要乘上的 \(10^l\) 也是确定的，我们只要将 \(mp_{(36 - t) \bmod {36}, Len(a_i)}\) 累加到答案中即可。

注意，当 \(t \equiv 36 - t \pmod {36}\) 时，我们会将本身也算上，而题目中不允许，从而我们需要减去 \(1\)。

时间复杂度：\(O(19n \log (19n))\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<string> a(n + 1);
    map<pii, int> cnt;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        int now = stoll(a[i]) % 36;
        for(int j=1;j<=20;j++) {
            now *= 10;
            now %= 36;
            cnt[{j, now % 36}] ++;
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++) {
        int now = stoll(a[i]);
        if(cnt.count({a[i].length(), (36 - now % 36) % 36})) {
            ans += cnt[{a[i].length(), (36 - now % 36) % 36}];
            if((36 - now % 36) % 36 == now % 36) ans --;
        }
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // init();
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

\(10^{18}\) 有 \(19\) 位（