题目大意

将 $l_i$ 个 $a_i$ 依次拼接在一起，结果对 $10^9+7$ 取模。

思路

假设答案为 $ans$，那么递推的方程为 $ans=ans\cdot 10^{\lfloor\log_{10}a_i\rfloor}+a_i$。

因为 $l_i$ 有 $10^9$ 进行模拟是不可行的，所以考虑使用矩阵快速幂加速递推。

$\begin{bmatrix} ans & a_i\end{bmatrix}=\begin{bmatrix} ans & a_i\end{bmatrix} \times \begin{bmatrix} 10^{\lfloor\log_{10}a_i\rfloor} & 0\\1&1\end{bmatrix}^{l_i}$

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+6;
struct node{
	int a[3][3];
	node(){
		memset(a,0,sizeof(a));
	}
}ans,aa;
int n,mod,a[N],l[N];
node times(node x,node y){
	node cnt;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++)
				cnt.a[i][j]=(cnt.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
		}
	}return cnt;
}node ksm(int x){
	while(x){
		if(x&1) ans=times(ans,aa);
		x>>=1;
		aa=times(aa,aa);
	}return ans;
}int f(int x){
	int cnt=0;
	while(x){
		cnt++;
		x/=10;
	}
	x=1;
	for(int i=1;i<=cnt;i++){
		x*=10;
	}
	return x;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>l[i];
	}
	cin>>mod;
	ans.a[1][1]=0;
	for(int i=1;i<=n;i++){
		ans.a[1][2]=a[i]%mod;
		aa.a[1][1]=f(a[i])%mod;
		aa.a[2][1]=aa.a[2][2]=1;
		ksm(l[i]);
	}
	cout<<ans.a[1][1]<<'\n';
	return 0;
}