题解 CF696C 【PLEASE】

· · 题解

推销博客

\mathcal{\color{Red}\colorbox{Black}{MY \ BLOG}}

思路分享

（你绝对想不到这篇题解的思路框架是初中数学）

根据初中数学的思想，我们遇到概率问题时可以考虑画一个状态树。

设一个三元组 \left( a_1,a_2,a_3 \right) 表示当前状态为 \left( a_1,a_2,a_3 \right)，若 a_i=0 则表示这个杯子没有钥匙，为 1 表示有钥匙。根据题意，显然 a_0+a_1+a_2=1。

然后我们就可以画出状态树：

我们可以发现，这个状态数是一棵二叉树。

让我们考虑二叉树每一个节点的子结点：

  1. 节点 (0,1,0) 的子结点有 0 个子结点是 (0,1,0)

  2. 节点 (1,0,0) 的子结点有 1 个子结点是 (0,1,0)

  3. 节点 (0,0,1) 的子结点有 1 个子结点是 (0,1,0)

这样有什么用呢？

由于树的根节点是初始状态，所以我们设其为第 0 层，然后我们考虑设 x_i 表示树的第 i 层的节点 (0,1,0) 的个数，就可以得到公式：x_i=2^{i-1}-x_{i-1}。

然后我们就可以求出答案：

ans_i=\dfrac{x_i}{2^{i}}=\dfrac{2^{i-1}-x_{i-1}}{2^{i}}=\dfrac{2^{i-1}-ans_{i-1}\times 2^{i-1}}{2^i}=\dfrac{1-ans_{i-1}}{2}=-\dfrac{1}{2}ans_{i-1}+\dfrac{1}{2}

从而得到：

ans_i-\dfrac{1}{3}=-\dfrac{1}{2}\left(ans_{i-1}-\dfrac{1}{3}\right)

最后就可以得到：

ans_n=-\dfrac{1}{3}\times\left(-\dfrac{1}{2}\right)^{n-1}+\dfrac{1}{3}

这时候我们就需要分考讨论

当 n 为偶数时：

ans_n=\dfrac{2^{n-1}+1}{2^{n-1}\times3}=\dfrac{\dfrac{\left(2^{n-1}+1\right)}{3}}{2^{n-1}}

当 n 为奇数时：

ans_n=\dfrac{2^{n-1}-1}{2^{n-1}\times3}=\dfrac{\dfrac{\left(2^{n-1}-1\right)}{3}}{2^{n-1}}

然后实现就很简单了。

代码展示

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Mod=1e9+7;
int n,a,b,parity;
int power(int x,int y){
    int ans=1;
    while(y){
        if(y&1){
            ans*=x;
            ans%=Mod;
        }
        x*=x;
        x%=Mod;
        y>>=1;
    }
    return ans;
}
signed main(){
    cin>>n;
    b=2;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a);
        b=power(b,a);
        parity=(parity)|(a%2ll==0ll);
    }
    b=b*power(2,Mod-2)%Mod;
    if(parity==1){
        printf("%lld/%lld",((b+1)*power(3,Mod-2))%Mod,b);
    }
    else{
        printf("%lld/%lld",((b-1+Mod)*power(3,Mod-2))%Mod,b);
    }
    return 0;
}