codeforces 696C PLEASE 概率dp+公式递推+费马小定理

题意：有3个杯子，排放一行，刚开始钥匙在中间的杯子，每次操作，将左右两边任意一个杯子进行交换，问n次操作后钥匙在中间杯子的概率

分析：考虑动态规划做法，dp[i]代表i次操作后的，钥匙在中间的概率，由于每次操作独立，dp[i]=(1-dp[i-1)/2;

         显然，dp[1]=0;

         由刚才那个式子可以得出：dp[i]-1/3=(-1/2)*(dp[i-1]-1/3)，这是高中数列知识

         然后 设dp[i]=p/q; dp[i]=(2^(n-1)+(-1)^n)/(3*2^(n-1))

         它要求p/q是最简分数，令p=（2^(n-1)+(-1)^n)/3,通过打表发现，（2^(n-1)+(-1)^n)可以被3整除，而且p是奇数

         q是2^(n-1)，是偶数，所以p/q等于dp[i],p,q互质，刚好符合题意，只能说这个题出的很好

         然后利用费马小定理求2^(n-1),求出3的逆元就好了，大部分都是推到，反而代码很简单

注：因为a[i]是在1到1e18之间的，所以要先取模，这个地方要注意

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int N  = 1e5+5;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9+7;
LL qpow(LL x,LL y){
  LL ret=1;
  while(y){
    if(y&1)ret=ret*x%mod;
    x=x*x%mod;
    y>>=1;
  }return ret;
}
int main(){
  int k;
  scanf("%d",&k);
  bool flag=false;
  bool flag1=false;
  LL n=1;
  for(int i=1;i<=k;++i){
    LL x;scanf("%I64d",&x);
    if(x%2==0)flag=true;  
    if(x>1)flag1=true;
    x%=(mod-1);
    n=n*x%(mod-1);
  }
  if(!flag1){
    printf("0/1
");
    return 0;
  }
  n=(n-1+mod-1)%(mod-1);
  LL q=qpow(2,n);
  LL inv3=qpow(3,mod-2);
  LL p=q;
  if(flag)p=(p+1)%mod;
  else p=(p-1+mod)%mod;
  p=p*inv3%mod;
  printf("%I64d/%I64d
",p,q);
  return 0;
}