题目描述

给定一个长度为 n 的数组 A1​,A2​,⋯,An​。你可以从中选出两个数 Ai​ 和 Aj​（i=j），然后将 Ai​ 和 Aj​ 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 Ai​ 和 Aj​ 的顺序总是被视为 2 种拼法，即便是 Ai​=Aj​ 时。

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

输入格式

第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A1​,A2​,⋯,An​。

输出格式

一个整数代表答案。

输入输出样例

输入 #1复制运行

4 2
1 2 3 4

输出 #1复制运行

6

说明/提示

对于所有评测用例，1≤n≤105，1≤k≤105，1≤Ai​≤109。

蓝桥杯 2020 第一轮省赛 B 组 I 题。

题意

很好理解，挑两个数拼起来看是不是k的倍数，直接暴力枚举嘛！O(n的平方) 哦吼！！超时啦！

那那那那那........怎么办

我们来想一个问题

一个数与另一个数拼起来，怎么变成加起来呢？比如1和2怎么拼 是不是就是在1后面加上2的位数个0呀 也就是10 + 2 = 12,变成加法就好判断是不是k的倍数了嘛

a%k==n,b%k==m,若n+m==k（或者n和m都为0）,则(a+b)%k==0，这个不用多说了吧

那么我们就可以将查找变成O(1)啦

我们定义一个二维数组ys[i][j] i代表位数，j代表余数

相信大家知道怎么预处理好数组，先算这个数的位数，再求这个数对k取余，放进去就好了嘛

我们来看样例

4 2

1 2 3 4

枚举每一个数,例如当前是1,我们首先找个数为1的数一直到个数为10的数

找个数为1的数 也就是让1*pow(10,1) 也就是10，样例中k是2,10%2=0，那么我们只要找到位数为1且余数为0有多少个不就可以了嘛

也就是ys[1][0]

全部统计起来就是答案

注意i!=j所以枚举每个数之前先将自己减去，统计完再加回来，而且不需要考虑交换，对于每个数除去了自己，就已经包括了所有交换顺序的情况

ac代码

#include<bits/stdc++.h>
using namespace std;
long long n,k,x,ans,sum;
long long ys[15][100005];
long long a[100005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        //求每个数的位数，以及对k取余,放入ys数组中
        x=a[i];
        ans=0;
        while(x>0){
            x/=10;
            ans++;
        }
        ys[ans][a[i]%k]++;
    }
    for(int i=1;i<=n;i++){
        //每次找之前需要先除掉自己，因为题目要求i!=j
        x=a[i];
        ans=0;
        while(x>0){
            x/=10;
            ans++;
        }
        ys[ans][a[i]%k]--;
        for(int j=1;j<=10;j++){
            x=a[i]*pow(10,j);
            if(x%k==0){
                sum+=ys[j][0];
            }else{
                sum+=ys[j][k-x%k];
            }
        }
        //统计完之后再复原
        ys[ans][a[i]%k]++;
    }
    cout<<sum;
}

很简单吧！！！创作不易！！！求支持！！！点赞！！！