Acwing 2068. 整数拼接（模运算）

题意：

给定一个长度为 n 的数组 A1,A2,⋅⋅⋅,An。 你可以从中选出两个数 Ai 和 Aj(i 不等于 j)，然后将 Ai 和 Aj 一前一后拼成一个新的整数。

例如 12 和 345 可以拼成 12345 或 34512。 注意交换 Ai 和 Aj 的顺序总是被视为 2 种拼法，即便是 Ai=Aj 时。

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

数据范围：1≤n≤1e5，1≤K≤1e5，1≤Ai≤1e9

解法：

$选取a[i],a[j],那么(a[i]\ast 10^{len(a[j])}+a[j])\%k=0$

$a[i]\ast 10^{len(a[j])}\%k+a[j]\%k=0$

$预处理cnt[len][x]表示满足a[i]\ast 10^{len}\%k=x的i的个数$

$对于每个a[j]，找满足a[i]\ast 10^{len(a[j])}\%k=(k-a[j]\%k)\%k的i的个数即可$

code：

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxm=1e5+5; ll a[maxm]; ll cnt[20][maxm]; ll p[maxm]; ll n,k; int getlen(int x){ int ans=0; while(x){ ans++,x/=10; } return ans; } signed main(){ scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } p[0]=1%k; for(int i=1;i<20;i++)p[i]=p[i-1]*10%k; for(int i=1;i<=n;i++){ for(int len=0;len<20;len++){ cnt[len][a[i]*p[len]%k]++; } } ll ans=0; for(int i=1;i<=n;i++){ for(int len=0;len<20;len++){//减掉自己防止匹配 cnt[len][a[i]*p[len]%k]--; } int len=getlen(a[i]); ans+=cnt[len][(k-a[i]%k)%k]; for(int len=0;len<20;len++){//加回去 cnt[len][a[i]*p[len]%k]++; } } printf("%lld\n",ans); return 0; }

---