题解 CF696C 【PLEASE】

2020-08-04 21:02:09


小清新推式子题,除快速幂外不需要任何算法。

定义 $1$ 为有钥匙的杯子, $0$ 为无钥匙的杯子,则有 $100,010,001$ 三种状态。

画出树状图:

第 $n$ 次移动后的答案为该层中状态为 $010$ 的节点个数除以该层总节点个数,设第 $n$ 次操作这一层中状态为 $010$ 的节点个数为 $A_n$,设第 $n$ 次移动后的答案为 $ans_n$,则 $ans_n=\dfrac{A_n}{2^n}$,得到 $A_n=ans_n\times2^n$。

每个 $010$ 节点的子节点中显然没有 $010$ 节点,每个非 $010$ 节点的子节点中有一个 $010$ 节点。

第 $n$ 次操作这一层中非 $010$ 节点的个数为 $2^n-A_n$,每个非 $010$ 节点对 $A_{n+1}$ 有 $1$ 的贡献,所以 $A_{n+1}=2^n-A_n$。

得到递推式: $ans_{n+1}=\dfrac{A_{n+1}}{2^{n+1}}=\dfrac{2^n-A_n}{2^{n+1}}=\dfrac{2^n-ans_n\times2^n}{2^{n+1}}=\dfrac{1-ans_n}{2}=-\dfrac{ans_n}{2}+\dfrac{1}{2}$。

从而得到: $-\dfrac{1}{2}(ans_n-\dfrac{1}{3})=ans_{n+1}-\dfrac{1}{3}$

设 $B_i=ans_i-\dfrac{1}{3}$,则 $B_{n+1}=-\dfrac{1}{2}B_n$,

$ans_1=0$, $B_1=ans_1-\dfrac{1}{3}=-\dfrac{1}{3}$,

$B$ 数列为等比数列, $B_1=-\dfrac{1}{3}$,得到通项公式: $B_n=(-\dfrac{1}{3})\times(-\dfrac{1}{2})^{n-1}$,

则 $ans_n=B_n+\dfrac{1}{3}=(-\dfrac{1}{3})\times(-\dfrac{1}{2})^{n-1}+\dfrac{1}{3}$。

当 $n$ 为奇数时, $ans_n=-\dfrac{1}{3}\times\dfrac{1}{2^{n-1}}+\dfrac{1}{3}=\dfrac{2^{n-1}-1}{3\times2^{n-1}}$,

题目要求将分数化为最简分数,显然分子不是 $2$ 的倍数,

设 $n=2t+1$( $t$ 为正整数), $2^{2}\equiv1\pmod{3}$,可得 $2^{2t}\equiv1\pmod{3}$, $2^{n-1}-1\equiv0\pmod{3}$,所以此时分子是 $3$ 的倍数。

即 $ans_n=\dfrac{(2^{n-1}-1)\div3}{2^{n-1}}$,此时为最简分数形式。

当 $n$ 为偶数时, $ans_n=\dfrac{1}{3}\times\dfrac{1}{2^{n-1}}+\dfrac{1}{3}=\dfrac{2^{n-1}+1}{3\times2^{n-1}}$,

显然分子不是 $2$ 的倍数,

设 $n=2t$( $t$ 为正整数), $2^{2}\equiv1\pmod{3}$,可得 $2^{2t-2}\equiv1\pmod{3}$, $2^{n-2}\equiv1\pmod{3}$, $2^{n-1}\equiv2\pmod{3}$, $2^{n-1}+1\equiv0\pmod{3}$,所以此时分子是 $3$ 的倍数。

即 $ans_n=\dfrac{(2^{n-1}+1)\div3}{2^{n-1}}$,此时为最简分数形式。

$n=\prod\limits_{i=1}^{k}a_i$, $2^n=(((2^{a_1})^{a_2})^{\dots})^{a_k}$。

快速幂 $+$ 逆元计算即可。

$\text{code}$:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int w=0,f=1;
    char c=' ';
    while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
    while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
    return w*f;
}
const int mod=1e9+7;
int pown(int x,int y){
    int res=1,ans=x;
    while(y){
        if(y&1)res=res*ans%mod;
        ans=ans*ans%mod;
        y>>=1;
    }
    return res;
}
signed main(){
    int n=read(),x,y=2;
    bool flag=0;
    for(int i=1;i<=n;i++)
        x=read(),flag=x%2?flag:1,y=pown(y,x)%mod;
    y=y*pown(2,mod-2)%mod;
    if(flag)printf("%lld/%lld",(y+1)*pown(3,mod-2)%mod,y);
    else printf("%lld/%lld",(y-1+mod)*pown(3,mod-2)%mod,y);
    return 0;
}