首页 > 代码库 > Codeforces 696 C. PLEASE

Codeforces 696 C. PLEASE

2024-08-26 00:59:22   218人阅读

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的逆元...

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;}

　　

Codeforces 696 C. PLEASE


联系
我们