题解 CF696C 【PLEASE】
Forever_Pursuit
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}$：
```cpp
#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;
}
```