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

const int INF = 0x3f3f3f3f;

const LL mod = 1e9+;

LL qpow(LL x,LL y){

  LL ret=;

  while(y){

    if(y&)ret=ret*x%mod;

    x=x*x%mod;

    y>>=;

  }return ret;

}

int main(){

  int k;

  scanf("%d",&k);

  bool flag=false;

  bool flag1=false;

  LL n=;

  for(int i=;i<=k;++i){

    LL x;scanf("%I64d",&x);

    if(x%==)flag=true;

    if(x>)flag1=true;

    x%=(mod-);

    n=n*x%(mod-);

  }

  if(!flag1){

    printf("0/1\n");

    return ;

  }

  n=(n-+mod-)%(mod-);

  LL q=qpow(,n);

  LL inv3=qpow(,mod-);

  LL p=q;

  if(flag)p=(p+)%mod;

  else p=(p-+mod)%mod;

  p=p*inv3%mod;

  printf("%I64d/%I64d\n",p,q);

  return ;

}

巴特西

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

最新文章

热门文章