以下では、文字列 \(S_i\) と、\(S_i\) を 10 進法で表された整数とみなした数を同一視します。

\(N\) を \(S_i\) ごとに分解して考えることにします。すなわち、例えば入出力例 1 であれば、\(N=1111\times 10^3+22\times 10^1+3\times 10^0\) と分解して考えます。これにより、問題を解くには各 \(S_i\) を \(M\) で割った余りと、\(10\) の累乗数を \(M\) で割った余りを求めることができれば十分であることがわかります。\(10\) の累乗数については容易なので、\(S_i\) についてを考えます。

\(S_i\) を \(M\) で割った余りは、桁数についてダブリングすることで求めることができます。すなわち、例えば \(111111\) を \(M\) で割った余りを求める問題であれば、\(111111=111\times 10^3 + 111\) と分解し、\(111\) を \(M\) で割った余りを求める問題に帰着し、再帰的に解きます。これは \(O(\log D_i)\) 時間で行えます。

以上により、\(D=\max(D_i)\) として、この問題は \(O(K\log D)\) で解けました。高速な言語であれば、\(O(K(\log D)^2)\) の解法でも実行時間制限に間に合わせることができる場合があります。

実装例(Python)

def f(x,a,m):
  """
  return
  base: pow(10,a,m) に等しい値
  ret: x を a 個連結してできる数を m で割った余り
  """
  if a==1:
    return 10%M,x
  base,ret=f(x,a//2,m)
  ret=(ret*base+ret)%m
  base=base*base%m
  if a%2:
    ret=(ret*10+x)%m
    base=base*10%m
  return base,ret


K,M=map(int,input().split())
ans=0
for i in range(K):
  c,d=map(int,input().split())
  base,ret=f(c,d,M)
  ans=(ans*base+ret)%M

print(ans)

実装例(C) 　\(O(K (\log D)^2)\) 解法

#define ll long long
#include<stdio.h>
ll pom(ll x,ll a,int m){
	// x の a 乗を m で割った余りを返す
	if(a==0)return 1;
	ll ret=pom(x,a/2,m);
	ret=ret*ret%m;
	if(a%2)ret=ret*x%m;
	return ret;
}

ll f(ll x,ll a,int m){
	// x を a 個連結してできる数を m で割った余りを返す
	if(a==1)return x;
	ll ret=f(x,a/2,m);
	ret=(ret*pom(10,a/2,m)+ret)%m;
	if(a%2)ret=(ret*10+x)%m;
	return ret;
}

int main(){
	int k,m;
	scanf("%d%d",&k,&m);
	ll ans=0;
	for(int i=0;i<k;i++){
		ll c,d;
		scanf("%lld%lld",&c,&d);
		ll ret=f(c,d,m);
		ans=(ans*pom(10,d,m)+ret)%m;
	}
	printf("%lld\n",ans);
}

なお、\(S_i = C_i (10^{D_i}-1)/9\) と表すことができるため、これを用いて \(\mod {9M}\) で適切に計算を行うことで解くこともできます。 実装例(Python)

k,m=map(int,input().split())
ans=0
for _ in range(k):
  c,d=map(int,input().split())
  ans=(ans*pow(10,d,m)+(pow(10,d,9*m)-1)//9*c)%m
print(ans)