[藍橋杯][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 ] × 10 ? l o g 10 a [ j ] ? + a [ j ] a [ i ] × 10 ? l o g 10 ? a [ j ] ? + a [ j ] a[i]×10?log10a[j]?+a[j]a[i]×10?log10?a[j]?+a[j] a[i]×10?log10a[j]?+a[j]a[i]×10?log10?a[j]?+a[j]

那要 a [ i ] × 10 ? l o g 10 a [ j ] ? + a [ j ] a [ i ] × 10 ? l o g 10 ? a [ j ] ? + a [ j ] a[i]×10?log10a[j]?+a[j]a[i]×10?log10?a[j]?+a[j] a[i]×10?log10a[j]?+a[j]a[i]×10?log10?a[j]?+a[j]是 k 的倍數，也就是要 a [ i ] × 10 ? l o g 10 a [ j ] ? % k + a [ j ] % k a [ i ] × 10 ? l o g 10 ? a [ j ] ? % k + a [ j ] % k a[i]×10?log10a[j]?\%k+a[j]\%ka[i]×10?log10?a[j]?\%k+a[j]\%k a[i]×10?log10a[j]?%k+a[j]%ka[i]×10?log10?a[j]?%k+a[j]%k 是 k 的倍數，

然后注意到 a [ i ] × 10 ? l o g 10 a [ j ] ? % k a [ i ] × 10 ? l o g 10 ? a [ j ] ? % k a[i]×10?log10a[j]?\%ka[i]×10?log10?a[j]?\%k a[i]×10?log10a[j]?%ka[i]×10?log10?a[j]?%k 這個數字是小于k的，而k最大是 1 0 5 10^{5} 105，
也就是說，我們是可以將其儲存起來的，

所以我們可以開一個cnt陣列，其中cnt[i][j]記錄在之前遍歷過的所有數中，乘 1 0 i {10^i} 10i后模 m 的結果為 j 的數的個數，
然后對于所有的a[i]，累加 c n t [ l o g 10 a [ i ] ] [ ( m ? a [ i ] % m ) % m ] cnt[log10a[i]][(m?a[i]\%m)\%m] 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;
}