AcWing周赛67 哈希表

这把..没有ak，第三题被卡了map和unordered_map，需要手写hash，前面两个题没什么好写的，直接写C吧..

比赛链接：AcWing周赛67

C.串联数字（哈希表）

题意：
给定 n 个正整数 a1,a2,…,an。

我们规定将正整数 ai 和 aj 串联是指将 aj 直接接在 ai 后面构成一个新整数。

例如，12 和 34 串联得到 1234，34 和 12 串联得到 3412。

现在，给定一个正整数 k，请你计算有多少个有序数对 (i,j)(i≠j) 满足，ai 和 aj 串联得到的整数能够被 k 整除。

思路：
对于当前的数，枚举10次，分别是往左边移动多少位，然后对$k$取余，进行计数。在这之前要先计算ans，思路不难，难得是优化常数。

需要手写hash，但是我不是很强，还是看y总代码吧：

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 200010, M = 10000007;

int n, m;
int a[N];
LL h[M];
int cnt[M];

int find(int r, int t)
{
    LL key = r * 100ll + t;
    int k = key % M;
    while (h[k] != -1 && h[k] != key)
        if ( ++ k == M)
            k = 0;
    if (h[k] == -1) h[k] = key, cnt[k] = 0;
    return k;
}

LL work()
{
    LL res = 0;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n; i ++ )
    {
        int r = a[i] % m;
        if (r) r = m - r;
        int t = 0, x = a[i];
        while (x) t ++, x /= 10;
        res += cnt[find(r, t)];

        for (int j = 1, x = 10; j <= 10; j ++, x = x * 10ll % m)
            cnt[find((LL)a[i] * x % m, j)] ++ ;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    LL res = work();
    reverse(a, a + n);
    res += work();

    printf("%lld\n", res);

    return 0;
}