Codeforces #362 Div1 C. PLEASE

しょうもないミスをする…。
http://codeforces.com/contest/696/problem/C

問題

３つのカップが横に並んでおり、初期状態で真ん中にコインが入っている。
１回処理を行うと、両端どちらかのカップを等確率で選び、真ん中のカップと入れ替える。
N回処理を行った後、真ん中にコインがある確率を有理数の形で答えよ。

なお、k要素の数列A[i]に対し、NはA[i]の積とする。

解法

３つカップがあるが、右と左を区別する必要はなく、真ん中かどうかだけ考えればよい。

• a(i) := i回処理後コインが真ん中のカップにある確率
• b(i) := i回処理後コインが真ん中以外のカップにある確率

と置くと、以下の数式が成り立つ。

• 
• 
• 

2つめの式を3つめの式に代入してbを消すとという普通の３項間漸化式になり、となる。
あとはa(N)を答えればよい。
(-1)^Nの部分はAの偶奇だけ考えればよいし、あとは分母の2^(N-1)の部分に注意。
Nは大きくなるが、2^(N-1) = 2^*1であることに注意して処理しよう。

int K;
ll mo=1000000007;
ll P,Q,X;
ll S,T;
int odd=-1;
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>>K;
	Q=1;
	T=1;
	FOR(i,K) {
		cin>>X;
		if(X==1) continue;
		if(X%2==0) odd=1;
		T=T*(X%(mo-1))%(mo-1);
	}
	
	Q=modpow(2,(T+mo-2)%(mo-1));
	P = (Q+mo+odd)*modpow(3) % mo;
	
	cout<<P<<"/"<<Q<<endl;
	
}

まとめ

(N-1)の計算で負の値を作ってしまいWA…。

*1:N-1)%(1000000007-1