PLEASE

题意：
有这么一个游戏，有三个杯子，每次可以使用中间的杯子与二边的交换，求n次交换后中间杯子还是原来那个的概率为多少？

思路：
设原来杯子用1表示，其余二个杯子用0表示：010为初始状况
第一次出现状态为：100、001
第二次出现状态为：100、010、010、001
第三次出现状态为：100、010、100、001、100、001、010、001
每一个状态可以演化成两个状态，所以第n次的总状态数为
由于010只由100、001一比一演化出，所以设 (当前次的010状态数等于上一次的总状态数减去上一次的010状态数)
第n次概率：
用高中知识去掉右边表达式的常数：

设:
所以：

代回去得：

最后n为奇数为：

最后n为偶数为：

我们发现分子一定为奇数，所以不会有2的因子，所以只需要考虑分子能不能被3整除，带几个n进去发现可以都整除3。
所以分子需要将分母的3除去。

参考：
https://blog.nowcoder.net/n/3d7a321601c845d5bfb99f469f5405c4
https://blog.nowcoder.net/n/fc44ba68be8444a7b6c4189f2b253457

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;
const int N=200005;

ll qpow(ll n, ll m)
{
    ll s=1;
    while(m)
    {
        if(m&1)
        {
            s=s*n%inf;
        }
        n=n*n%inf;
        m=m/2;
    }
    return s;
}

int main()
{
    int k;
    scanf("%d",&k);
    ll p=2;
    int flag=1;
    for(int i=0;i<k;i++)
    {
        ll a;
        scanf("%lld",&a);
        p=qpow(p,a);
        if(a%2==0)
        {
            flag=0;
        }
    }
    p=p*qpow(2LL,inf-2)%inf;
    ll ki=qpow(3LL,inf-2);
    if(flag)
    {
        printf("%lld/%lld\n",(p-1+inf)%inf*ki%inf,p);
    }
    else
    {
        printf("%lld/%lld\n",(p+1)%inf*ki%inf,p);
    }
    return 0;
}