Submarine in the Rybinsk Sea (hard edition)

Created by LXC on Tue May 16 08:33:58 2023

https://codeforces.com/problemset/problem/1195/D2

ranting: 1800

tag: combinatorics, math, number theory

题意

设$x = \overline{x_px_{p-1}\cdots x_{0}},y = \overline{y_qy_{q-1}\cdots y_{0}}$

当$p>q$时，函数$f(x,y) = x_p\cdots x_qy_qx_{q-1}y_{q-1}\cdots x_0y_0$

当$p<=q$时，函数$f(x,y) = x_q\cdots x_py_px_{p-1}y_{p-1}\cdots x_0y_0$

现在给出一个长度为$n$的数组$a$，$a_i\le 1e^9, n\le 100000$

求$\sum \limits_{x=1}^{n} \sum \limits_{j=1}^{n} f(a_i, a_j)$

题解

考虑每个数拆位后的贡献。

数组中的某个p位十进制数$a_k=\overline{t_pt_{p-1}\cdots t_{0}}$作为$f(x,y)$的$y$，贡献的答案与x的长度有关。

当x长度为1，则为答案贡献数值$\overline{t_pt_{p-1}\cdots t_1 0 t_{0}}$。

当x长度为2，则为答案贡献数值$\overline{t_pt_{p-1}\cdots t_2 0 t_1 0 t_{0}}$。

当x长度为i，则为答案贡献数值$\overline{t_pt_{p-1}\cdots t_i 0 \cdots 0 t_{0}}$。

实际上x的长度不超过10，我们可以预处理出数组中所有长度出现的次数。记为$c_i$，长度为i的元素出现的次数。

这样所有长度为i的x，与$a_k$作为y值的贡献就是$\overline{t_pt_{p-1}\cdots t_i 0 \cdots 0 t_{0}}\times c_i$

同理我们也可以求出$a_k$作为x的贡献值。

这样时间复杂度就是$O(np)$,p是数值最大位数。

代码

#include <bits/stdc++.h>
// #define LOCAL
#define SINGLE_INPUT
#define ll unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    cin >> n;
    vector<string> a(n);
    vector<int> c(11);
    for (string& i : a) {
        cin >> i;
        reverse(i.begin(), i.end());
        c[i.size()]++;
    }
    // for (int i = 1; i < 12; i++) {
    //     cout << i << " " << c[i] << "\n";
    // }
    ll ans = 0;
    for (string i : a) {
        // cout << i << ": ";
        int sz = i.size();
        string low1, low2;
        for (int j = 0; j < 10; j++) {
            low1.push_back(j < sz ? i[j] : '0');
            low1.push_back('0');
            string t1 = low1 + i.substr(min(j + 1, sz));
            reverse(t1.begin(), t1.end());
            ll num1 = stoull(t1);
            // cout << j + 1 << "-- " << num1 << ", ";
            ans += num1 % MOD * c[j + 1] % MOD;
            ans %= MOD;

            low2.push_back('0');
            low2.push_back(j < sz ? i[j] : '0');
            string t2 = low2 + i.substr(min(j + 1, sz));
            reverse(t2.begin(), t2.end());
            ll num2 = stoull(t2);
            // cout << j + 1 << "-- " << num2 << ", ";
            ans += num2 % MOD * c[j + 1] % MOD;
            ans %= MOD;
        }
        // cout << "\n";
    }
    cout << ans << "\n";
}

int main() {
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed;
#endif

    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif

#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: "
         << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
    return 0;
}