CF696C PLEASE 解题报告(推式子+欧拉降幂+细节)
PLEASE
https://ac.nowcoder.com/acm/problem/111563
首先,根据题目要求,因为每一轮都需要把中间给替换掉可知,要想最终钥匙在中间,那么在最后一轮之前钥匙一定不能在中间。又因为一轮可以把中间替换成任意一个非中间元素,再加上经过n轮每轮一共有2种决策,所以共有种局面。所以,得到递推式:。
之后,考虑我们要求的答案ans,则有:,要求,考虑求其通项公式,则,代替带入上式: ,这个高中做过不少了吧?得到。
这里若不考虑符号,则上下可能都为负数,此时再去+mod之后的结果是上下分别mod之后的结果,不符合题意,因此,我们需要讨论下符号。
当n为奇数:
n为偶数:
考虑细节:(n为偶数)和(n为奇数)mod 3都为0(打表试试?),所以,3应该放在分子处*3的逆元。
AC代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<typename T> void read(T&x){ x=0; int f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')f*=-1; ch=getchar(); } while(isdigit(ch)){ x=x*10+(ch-'0'); ch=getchar(); }x*=f; } template<typename T> void write(T x){ if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0'); } //=============================================== #define int ll const int maxn=1e5+10; const int mod=1e9+7; ll k,a[maxn]; #define mu(x) (x-1) ll ksm(ll a,ll n,ll p){ ll res=1; while(n){ if(n&1)res=res*a%p; a=a*a%p; n>>=1; } return res; } signed main(){ int mup=mu(mod); //freopen("in.txt","r",stdin); read(k); for(int i=1;i<=k;++i)read(a[i]),a[i]%=mup; ll n=1; for(int i=1;i<=k;++i)n=1ll*n*a[i]%mup; ll tim=((n-1)%mup+mup)%mup; if(tim==0)tim=mup; if(n&1){ ll up=((ksm(2,tim,mod)-1)%mod+mod)%mod; up=(up)*ksm(3,mod-2,mod)%mod; ll down=((ksm(2,tim,mod))%mod+mod)%mod; cout<<up<<"/"<<down<<endl; } else{ ll up=((ksm(2,tim,mod)+1)%mod+mod)%mod; up=up*ksm(3,mod-2,mod)%mod; ll down=(ksm(2,tim,mod)%mod+mod)%mod; cout<<up<<"/"<<down<<endl; } return 0; }