蓝桥杯 整数拼接

题目链接

问题描述

给定一个长度为 n 的数组 A₁ , A₂ ,⋅⋅⋅, A_n 。

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

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

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

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

输入格式

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

第二行包含 n 个整数 A₁ , A₂ ,⋅⋅⋅, A_n 。

输出格式

一个整数代表答案。

数据范围

1≤ n ≤10⁵
1≤ K ≤10⁵
1≤ A_i ≤10⁹

输入样例：

4 2
1 2 3 4

输出样例：

6

分析

求拼接数为k的倍数的个数。感觉跟Post not found: 蓝桥杯-k倍区间 蓝桥杯-k倍区间有点像。于是思路往那边靠拢。(瞄了一眼数据范围暴力明显不行，且有思路，就先不写暴力了)

按照题目大意，两个拼接数可以表示成如下形式：

$S=a[i]×10^{log_{10}a[j]}+a[j]$

那么求S是否是k的倍数，就可以转换为求

$(a[i]×10^{log_{10}a[j]} \quad \% \quad k) \quad =\quad (a[j]\%k)$

的配对数。这个求解过程，跟Post not found: 蓝桥杯-k倍区间 蓝桥杯-k倍区间是一样的，这里不做过多赘述。

不同的是，这里对于每个a[i]，都需要乘于一个系数 10^{log₁₀a[j]} 。我们虽然不能预知每一个数的位数，但由1≤ A_i ≤10⁹可以得到a[i]的位数的取值范围在【1，10】之间。即:

$Power \in 10^{[0,10]}$

因此我们可以把 乘于的每种系数提出来单独讨论，即分成11种情况来讨论。

设 **F_i,j **为 每个数乘于10ⁱ与k取模后等于j的个数，ans为总拼法。那么就有：

$ans=ans+cnt[\ log_{10}a[j]\ ][\ (a[i]\ × 10^{log_{10}a[j]}) \ \% \ k \ ]$

其中 i<j ,a[i]为高位部分，a[j]为低位部分。

而根据上述等式，我们根本不需要知道a[i]的数值，只需要处理 a[j] 本身的位数对模数的影响就可以了，推导过程如下：

(a[i]\ × 10^{log_{10}a[j]}\ +\ a[j]) \ \% \ k \ =\ 0 \\ (a[i]\ × 10^{log_{10}a[j]})\ \% \ k\ \ =\ -a[j] \ \% \ k \\ (a[i]\ × 10^{log_{10}a[j]})\ \% \ k\ \ =\ (k-a[j] \ \%\ k)\ \%\ k\

这样，我们就可以用 ( k - a[j] % k) % k代替 10^{log₁₀a[j]} 。解决需要两个变量的问题。

当然，上述做法只能完成**a[i]<a[j]**时，即:a[i]a[j]的拼接情况，不能解决a[j]a[i]的拼接情况。

解决方式也十分简单，让序列反过来按上述流程再说一遍就好了。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int f[20][N];
int a[N];
LL ans;
int n,k; 
int log_10(int x){
	int res = 0;
	while(x){
		res++;
		x/=10;
	}
	return res;
}
void work(){
	for(int i=0;i<n;i++){
		
		ans+=f[log_10(a[i])][(k-a[i]%k)%k];
		
		for(int j=0,index = 1;j<11;j++){
			f[j][(LL)index*a[i]%k]++;
			index=(index *10)%k;//其实直接index*=10好像也可以 
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	
	work();
	
	reverse(a,a+n);
	memset(f,0,sizeof f);
	
	work();
	
	cout<<ans<<endl;
	return 0; 
}