整数拼接(枚举，哈希表，数学)

本文主要是介绍整数拼接(枚举，哈希表，数学)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接:https://www.acwing.com/problem/content/2070/

题目
给定一个长度为 n n n 的数组 A 1 , A 2 , ⋅ ⋅ ⋅ , A n A_1,A_2,⋅⋅⋅,A_n A1​,A2​,⋅⋅⋅,An​。

你可以从中选出两个数 A i A_i Ai​ 和 A j A_j Aj​(i 不等于 j)，然后将 A i A_i Ai​ 和 A j A_j Aj​ 一前一后拼成一个新的整数。

例如 12 12 12 和 345 345 345 可以拼成 12345 12345 12345 或 34512 34512 34512。

注意交换 A i A_i Ai​ 和 A j A_j Aj​ 的顺序总是被视为 2 种拼法，即便是 A i = A j A_i=A_j Ai​=Aj​ 时。

请你计算有多少种拼法满足拼出的整数是 K K K 的倍数。

输入格式
第一行包含 2 2 2 个整数 n n n 和 K K K。

第二行包含 n n n 个整数 A 1 , A 2 , ⋅ ⋅ ⋅ , A n A_1,A_2,⋅⋅⋅,A_n A1​,A2​,⋅⋅⋅,An​。

输出格式
一个整数代表答案。

数据范围
1 ≤ n ≤ 1 0 5 , 1≤n≤10^5, 1≤n≤105,
1 ≤ K ≤ 1 0 5 , 1≤K≤10^5, 1≤K≤105,
1 ≤ A i ≤ 1 0 9 1≤A_i≤10^9 1≤Ai​≤109

输入样例：

4 2
1 2 3 4

输出样例：

6

A j A i A_jA_i Aj​Ai​拼接起来的数可以表示为 A j l e n ( A i ) + A i A_j^{len(A_i)}+A_i Ajlen(Ai​)​+Ai​
因为是 K K K的倍数，所以有 A j t + A i = 0 ( m o d   k ) A_j^t+A_i = 0 \quad (mod\ k) Ajt​+Ai​=0(mod k)
即 A j l e n ( A i ) = − A i ( m o d   k ) A_j^{len(A_i)}= -A_i \quad (mod\ k) Ajlen(Ai​)​=−Ai​(mod k)
可以用十一个哈希表存储 A j ∗ 1 0 t ， t ∈ [ 0 , 10 ] A_j * 10^{t}，t \in [0,10] Aj​∗10t，t∈[0,10] 模 k k k 的值
接着只需要枚举每个 A i A_i Ai​，看有多少个 A j l e n ( A i )   %   k = − A i   %   k A_j^{len(A_i)} \ \%\ k = -A_i \ \%\ k Ajlen(Ai​)​ % k=−Ai​ % k 即可
注意:
①因为负数取模，c++中得到的是负数，数学上定义的是正数
比如
− 5   %   2 = − 3 ∗ 2 + 1 -5 \ \%\ 2 = -3 * 2 + 1 −5 % 2=−3∗2+1 因此 − 5   %   2 = 1 -5 \ \%\ 2 = 1 −5 % 2=1
− 1   %   4 = − 1 ∗ 4 + 3 -1 \ \%\ 4 = -1 * 4 + 3 −1 % 4=−1∗4+3 因此 − 1   %   4 = 3 -1 \ \%\ 4 = 3 −1 % 4=3
要取得 − a   %   k -a \ \%\ k −a % k 的正数，即 ( k − a )   %   k (k - a) \ \%\ k (k−a) % k

② A j A_j Aj​和 A i A_i Ai​是同一个数的情况，即 j = i j = i j=i，答案要减1

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

LL n,k,ans;
int arr[N],s[11][N];

int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&arr[i]);
        LL t = arr[i] % k;
        for(int j = 0; j < 11; j++)
        {
            s[j][t]++;
            t = t * 10 % k;
        }
    }
    for(int i = 0; i < n; i++)
    {
        LL t = arr[i] % k;
        LL mod = (k - t) % k; //因为负数取模，c++中得到的是负数，要取得正数
        int len = to_string(arr[i]).size();
        ans += s[len][mod];
        LL r = t;
        while(len--) r = r * 10 % k;
        if(r == mod) ans --;
    }
    printf("%lld\n",ans);
    return 0;
}

这篇关于整数拼接(枚举，哈希表，数学)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！