Codeforces #191 Div2. C. Magic Five

CF191はDiv2 Onlyなので不参加で練習のみ。
http://codeforces.com/contest/327/problem/C

問題

0-9で構成されるA桁の文字列をK回繰り返したとても長い文字列がある。
ここから何文字か抜いて5の倍数となる組み合わせ数を求めよ。
ただしleading 0があっても良い。

解法

i桁目の数字が0か5だとすると、その桁より下を消してしまえば５の倍数になる。
i桁目より上はあってもなくてもいいので、2^(A*K-1)通り。

ただ、A*Kは10^14まで行くので、全桁チェックはできない。
幸い数字はA桁の繰り返しなのでうまく計算量を落としていく。
先頭A桁までのi桁が0か5の時、(i+A)、(i+2A)、…、(i+(K-1)A)桁も0か5なのでこれらの組み合わせ数は
2^i + 2^(i+A) + 2^(i+2A) + ... +2^(i+(K-1)A) = ((2^AK)-1) * 2^i /(2^A)
で求められる。

// a^n % p
ll mo=1000000007;
ll modpow(ll a, ll n, ll p) {
	ll r=1;
	while(n) {
		if(n%2) r=(r*a)%p;
		a=(a*a)%p;
		n>>=1;
	}
	return r;
}
ll rev(ll num) {
	ll pw = mo-2;
	ll ret = 1;
	for(ll i = 30; i >= 0; i--) {
		ret = (ret*ret)%mo;
		if((pw>>i)&1) ret = (ret*num)%mo;
	}
	return ret;
}

string S;
ll K;

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty;
	ll res=0;
	cin >> S >> K;
	
	FOR(i,S.size()) if(S[i]=='0' || S[i]=='5') {
		res = (res + (((modpow(2,S.size()*K,mo)-1)*rev(modpow(2,S.size(),mo)-1))%mo)*modpow(2,i,mo)) % mo;
	}
	cout << res << endl;
	return;
}

まとめ

leading 0が不許可だったら難しいのかな。