Codeforces ECR #013 : D. Iterated Linear Function

この回はECRだけど妙に難しかった。
http://codeforces.com/contest/678/problem/D

問題

整数A,Bに対し関数f(x)=Ax+Bを考える。
f^n(x)を答えよ。

解法

• A==1の時、f(x)=x+Bなので f^n(x)=x+nB
• A＞1の時、f^n(x) = a^n + (a^(n-1)+a^(n-2)+...+1)B = a^n + (a^n-1)/(a-1)B

上記を愚直に計算すればよい。

ll A,B,N,X;
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	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>>A>>B>>N>>X;
	ll ret=modpow(A,N)*X%mo;
	
	ll hoge;
	if(A==1) hoge=N%mo;
	else {
		ll Ap=(modpow(A,N)+(mo-1))%mo;
		ll re=modpow(A-1);
		hoge=Ap*re%mo;
	}
	
	ret += hoge*B%mo;
	cout<<ret%mo<<endl;
	
	
}

まとめ

本番１か所剰余を取り忘れてWAした。