Codeforces #475 A. Alternating Sum

ここ数回CFのRated回の出来がひどい。
http://codeforces.com/contest/963/problem/A

問題

整数N,A,Bが与えられる。
Sを1または-1のいずれかを持つ長さ(N+1)の数列とする。

ここでを(10^9+9)で割った剰余を求めたい。
Nは非常に大きいが、Sは長さKのパターンを(N+1)/K回繰り返したものとする。
長さKのパターンが与えられるので、上記値を求めよ。

解法

上記Sumの先頭K要素の和をとする。
解はとおくととなるので等比数列の和を求めればよい。
rが1となる場合は安易に等比数列の和の公式を使わないよう気を付けよう。

int N,A,B,K;
string S;
ll mo=1000000009;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>K;
	cin>>S;
	
	ll ret=0;
	FOR(i,K) {
		ll v=modpow(A,N-i)*modpow(B,i)%mo;
		if(S[i]=='-') v=mo-v;
		ret+=v;
	}
	ret%=mo;
	
	ll ba=modpow(B*modpow(A)%mo,K);
	ll nk=(N+1)/K;
	
	if(ba==1) {
		ret*=nk;
	}
	else {
		ret=ret*(modpow(ba,nk)+mo-1)%mo*modpow(ba-1);
	}
	cout<<ret%mo<<endl;
	
}

まとめ

まぁこれはとくに迷わず。