【CodeForces-1029D】Concatenated Multiples

【CodeForces-1029D】Concatenated Multiples

问题链接:http://codeforces.com/problemset/problem/1029/D

Solution:

原来自己没有解决,参照了别人写的题解:http://codeforces.com/blog/entry/61439

首先分析组合后的数:\(a_i * 10^{len_j} + a_j\),这个数如果要被k整除,则必要加号两侧各自被k除后的余数都是0或者相加为k,接下来就是关键的处理步骤了。

如果我们暴力每个i、j,复杂度将是\(O(n^2)\)的,根据这道题的数据范围,规模会达到4e10,所以我们不能采用暴力来解决。参照上边链接内的题解,给出了一种方案,因为我们需要的只是在确定长度时等于0(当\(a_i * 10^{len_j} % k = 0\)时 )或等于\(k – a_i * 10^{len_j} % k\)(当\(a_i * 10^{len_j} % k \neq 0\)时)的\(a_j % k\)的数量,那么为每一种a[i]长度开一个vector,其中存储一下该长度的a[i]对k取模后的值,接着在这里使用它来作为a[j],排序后,可以使用二分搜索来确定索引上下界,索引上界减去索引下界就是数量,之后再判断一下是否包含的当前枚举的a[i]自身就好【如果包含,要将ans–】

根据这个设计,我写的代码是这样:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), rem ? k - rem : 0);
            ans += r - l;
            if (j == digits[i] && (rem ? k - rem : 0) == data[i] % k) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}

rem ? k – rem : 0这个写起来太麻烦了,按照题解的做法,可以改成:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;
const int LIM = 2e5 + 10;
const int LENGTH = 11;
LL data[LIM], digits[LIM];
LL table[LENGTH];
vector<LL> remain[LENGTH];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    LL n, k;
    cin >> n >> k;
    table[0] = 1;
    for (int i = 1; i < LENGTH; i++)
        table[i] = table[i - 1] * 10 % k;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        LL tmp = data[i];
        digits[i] = 0;
        while (tmp) {
            tmp /= 10, digits[i]++;
        }
        remain[digits[i]].push_back(data[i] % k);
    }
    for (int i = 0; i < LENGTH; i++)
        sort(remain[i].begin(), remain[i].end());
    LL ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < LENGTH; j++) {
            LL rem = data[i] * table[j] % k;
            vector<LL>::iterator l = lower_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            vector<LL>::iterator r = upper_bound(remain[j].begin(), remain[j].end(), (k - rem) % k);
            ans += r - l;
            if (j == digits[i] && (rem + data[i] % k) % k == 0) ans--;
        }
    }
    cout << ans << "\n";
    return 0;
}