Description
三个杯子,一开始钥匙在中间,每次等概率的选择两边的两个,与中间的交换,问第 (n) 次选择中间的杯子是钥匙的概率是多少.
(n=sum_{i=1}^{k} a_i,a_ileqslant 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}), ext{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))
显然他可以整除3,同时他是个奇数,没有2的因子.
这样就完成了证明,所以直接在分子乘3的逆元即可.
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;
}