Codeforces Round #506 (Div. 3) - D. Concatenated Multiples（思维拼接求是否为k的倍数）

题意

给你N个数字和一个K，问一共有几种拼接数字的方式使得到的数字是K的倍数，拼接：“234”和“123”拼接得到“234123”

分析：

• N <= 2e5,简单的暴力O（N^2）枚举肯定超时
• 数字A和B拼接，B的位数最多10位，如果我们知道位数为（1-10）的数字和A拼接满足是K的倍数这样的数字有几个，就可以在N*10的复杂度下完成所有的拼接
• 在读入数据的时候，我们可以统计出数字的位数和对K取余的结果，这样我们就可以在O(1)的时间内得到所有满足的情况

#include<bits/stdc++.h>

#include <iostream>

#include <cmath>

#include <map>

#include <vector>

#include <set>

#include <algorithm>

#define ll long long

#define ull unsigned long long

#define N 200005

using namespace std;

ll a[N];

// 获取长度

int getlen(int x) {

    int sum = ;

    while (x) {

        ++sum;

        x /= ;

    }

    return sum;

}

map<int, int> mp[];

int main() {

    int n, k;

    while (scanf("%d%d", &n, &k) != EOF) {

        for (int i = ; i < n; ++i) {

            scanf("%lld", &a[i]);

            int len = getlen(a[i]);

            mp[len][a[i] % k]++;

        }

        ll ans = ;

        // 枚举N个数字

        for (int i = ; i < n; ++i) {

            ll mul = ;

            int len = getlen(a[i]);

            mp[len][a[i] % k]--;

            // 对每个数字，分别对位数为 j 的数字进行拼接

            for (int j = ; j <= ; ++j) {

                mul *= ;

                ull temp = a[i] * mul;

                if (mp[j].find((k - temp % k) % k) != mp[j].end())

                    ans += mp[j][(k - temp % k) % k];

            }

            mp[len][a[i] % k]++;

        }

        printf("%I64d\n", ans);

        for (int i = ; i < ; ++i)

            mp[i].clear();

    }

    return ;

}