Codeforces 696 C. PLEASE

Description

三個杯子,一開始鑰匙在中間,每次等機率的選擇兩邊的兩個,與中間的交換,問第 \(n\) 次選擇中間的杯子是鑰匙的機率是多少.

\(n=\sum_{i=1}^{k} a_i,a_i\leqslant 10^{18}\)

Sol

機率DP.

首先 \(a_i\) 表示在中間的機率, \(b_i\) 表示不再中間的機率.

那麼 \(a_i=\frac{1}{2}b_{i-1},b_i=1-\frac{1}{2}b_{i-1}\) .

對于 \({b_n}\) 數列,可以解個方程變成等比數列,然後就可以搞出來通項公式了.

\(b_n-\frac {2}{3}=-\frac {1} {2} (b_{i-1}-\frac{2}{3})\)

\(b_n=(-\frac{1}{2})^n(b_0-\frac {2} {3})+\frac {2} {3}\)

那麼 \(a_n=1-b_n\)

就是 \(a_n=\frac {2^n+2*(-1)^{n}}{3*2^{n}}\)

主要是最後的那個約分比較難搞..

首先對指數用歐拉定理取膜.

上下通除一個2,在分子上乘3的逆元...

為什麼這樣做是對的呢...

首先除一個2肯定是沒有問題的,因為分子分母都含一個2,現在來證明分子整除3

兩個式子時 \(n\) 次方差公式.

\(a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+...+a^2b^{n-3}+ab^{n-2}b^{n-1})\)

\(a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-...+a^2b^{n-3}-ab^{n-2}+b^{n-1}),\text{n is an odd number}\)

當 \(n-1\) 為奇數時

\(2^{n-1}+1=(2+1)(2^{n-2}-2^{n-3}+2^{n-4}...+1)\)

顯然他可以整除3,同時他是個奇數,沒有2的因子.

當 \(n-1\) 為偶數時

那麼 \(2^{n-1}-1\) 可以表示成 \(2^{2^x}-1\)

是以有 \(2^{2^x}-1=(4-1)(2^{2^{x-1}}+2^{2^{x-2}}...+1)\)

Code

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

#define debug(a) cout<<#a<<"="<<a<<" "
typedef long long LL;
const LL p = 1000000007;

LL k,x;
LL _2n,a,b,f;

LL Pow(LL a,LL b,LL res=1){ for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;return res; }
int main(){
	ios::sync_with_stdio(false);
	cin>>k;
	_2n=1,f=1;
	for(int i=1;i<=k;i++){
		cin>>x;
		x=x%(p-1);
		_2n=(_2n*x)%(p-1);
		f&=(x&1);
	}
	_2n=Pow(2,(_2n-1+p-1)%(p-1));
	if(f) f=-1;else f=1;
	
//	debug(_2n),debug(f)<<endl;
//	debug(Pow(3,p-2))<<endl;
	
	a=(_2n+f+p)%p*Pow(3,p-2)%p;
	b=_2n%p;
	if(!a) cout<<"0/1"<<endl;
	else cout<<a<<"/"<<b<<endl;
	return 0;
}