[藍橋杯][2020年第十一屆真題第一場]整數拼接

題目描述：

給定一個長度為 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≤n≤105, 1≤K≤105, 1≤Ai≤109

輸入樣例： 4 2 1 2 3 4
輸出樣例： 6

解題思路：

考慮如何快速求出與a[i]拼接起來為k的倍數的數位。

要與a[i]拼接起來是k的倍數，那首先要考慮a[i]和a[j]拼起來是個啥玩意。

觀察到a[i]與a[j]拼起來的結果即為 $$a[i]\times 10\lfloor log10a[j]\rfloor +a[j]a[i]\times 10\lfloor log10a[j]\rfloor +a[j]$$

那要$$a[i]\times 10\lfloor log10a[j]\rfloor +a[j]a[i]\times 10\lfloor log10a[j]\rfloor +a[j]$$是 k 的倍數，也就是要 $$a[i]\times 10\lfloor log10a[j]\rfloor \%k+a[j]\%ka[i]\times 10\lfloor log10a[j]\rfloor \%k+a[j]\%k$$ 是 k 的倍數。

然後注意到 $$a[i]\times 10\lfloor log10a[j]\rfloor \%ka[i]\times 10\lfloor log10a[j]\rfloor \%k$$ 這個數位是小於k的，而k最大是 $10^5$。
也就是說，我們是可以將其儲存起來的。

所以我們可以開一個cnt陣列，其中cnt[i][j]記錄在之前遍歷過的所有數中，乘 $10^i$後模 m 的結果為 j 的數的個數。
然後對於所有的a[i]，累加 $$cnt[log10a[i]][(m-a[i]\%m)\%m]$$即可。

但這隻能求出所有 i<ji<j 的合法的 a[i] 與 a[j] 的個數。
從前往後跑一遍，從後往前再跑一遍就可以

#include<bits/stdc++.h>
#define x first
#define y second
#define mem-1(h) memset(h,-1,sizeof h)
#define mem0(h) memset(h,0,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
	inline LL read(){
		LL o=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
		while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
		return o*f;
	}
}using namespace IO;
//#############以上是自定義技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
LL ans;
int a[N];
int cnt[12][N];
int n,k;
int log_10(int x){
	int res=0;
	while(x){
		x/=10;
		res++;
	}
	return res;
}
void solve(){
	for(int i=0;i<n;i++){
		ans+=cnt[log_10(a[i])][(k-a[i]%k)%k];
		for(int j=0,pow=1;j<11;j++){
			cnt[j][pow*1ll*a[i]%k]++;
			pow=pow*10%k;
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	solve();
	mem0(cnt);
	reverse(a,a+n);
	solve();
	cout<<ans<<endl;
	return 0;
}