AtCoder ARC #020 : C - A mod B Problem

何とか本番中に解けてよかった。
http://arc020.contest.atcoder.jp/tasks/arc020_3

問題

配列a[i]とL[i]から生成される巨大数Aがある。
巨大数Aはa[i]をL[i]回繰り返したものを文字列的に連結することで生成する。

巨大数AをBで割った余りを答えよ。

解法

a[i]の桁数をD[i]、a[i+1]・L[i+1]以降で生成される数字の桁数をS[i]とする。
a[i]とL[i]から生成される数字の部分は以下のように生成できる。

a[i]はintの範囲なのでa[i]%Bの値は簡単に求められる。
また、(10^S[i])%Bも繰り返し自乗法で簡単に求められる。

問題は真ん中の等比数列の部分である。
等比数列の和の公式を使うとこの部分について以下の式が成り立つ。

部分点を取るなら、Bが素数なのでフェルマーの小定理から(10^d-1)の逆元を求めて掛け合わせればよい。

Bが素数でない場合、この除算ができない。
一方以下の手順で項数を半々にすることで、T(l,d)はO(log l log d)で求めることができる。

• とすると：
  • Lが偶数のとき
  • Lが奇数の時

int N;
ll A[10001],D[10001],L[10001],S[10001];
ll RD[12];
ll B;

ll calc(ll dig,ll momo) {
	ll v=1;
	ll cur=10;
	while(dig) {
		if(dig%2) v=(v*cur)%momo;
		cur=(cur*cur)%momo;
		dig>>=1;
	}
	return v;
}

ll rev(ll num, ll momo) {
	ll pw = momo-2;
	ll ret = 1;
	for(ll i = 30; i >= 0; i--) {
		ret = (ret*ret)%momo;
		if((pw>>i)&1) ret = (ret*num)%momo;
	}
	return ret;
}

ll calc2(ll D,ll L,ll B) {
	if(L<=1) return L;
	if(L==1) return 1;
	
	ll vv = calc2(D,L/2,B)*(1+calc(D*(L/2),B))%B;
	if(L%2) vv=(vv+calc(D*(L-1),B))%B;
	return vv;
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) cin>>A[i]>>L[i];
	cin>>B;
	FOR(i,N) {
		ll hoge=A[i];
		while(hoge) D[i]++,hoge/=10;
	}
	
	ll cc=9;
	for(i=1;i<=11;i++) RD[i]=rev(cc,B),cc=cc*10+9;
	
	for(i=N-2;i>=0;i--) S[i]=S[i+1]+L[i+1]*D[i+1];
	ll ret=0;
	FOR(i,N) ret+=calc2(D[i],L[i],B)*calc(S[i],B)%B*A[i]%B;
	cout << ret%B << endl;
	
}

まとめ

本番、自分も最初99pt狙いで10^d-1の逆元を取り、その後分割による等比数列の総和を取る方法を思いついた。