NOIP前最后的博客。
B.万物有灵
发现一定是从最后一层开始选，然后隔一层选。所以 \(n\) 的奇偶性与选所有下标的奇偶性相同。为了避免分类讨论，可以将周期乘以 2。然后发现是一个等比数列求和。因为模数可能不是质数，就直接倍增维护 \(f_i\) 表示 \(x^1+x^2+...x^{2^i}\)，\(g_i\) 表示 \(x^{2^i}\)。然后就可以 $k + log n $ 做了。
点击查看代码
#include<bits/stdc++.h>
using ll=long long;
ll n,p,k;
ll a[1000005],b[1000005];
ll qpow(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
return ans;
}
ll f[1000005],g[1000005];
ll solve(ll start,ll bs,ll m){
if(m<0)return 0;
ll ans=0,res=1;
f[0]=g[0]=bs;
for(int i=1;i<=60;++i)g[i]=g[i-1]*g[i-1]%p;
for(int i=1;i<=60;++i)f[i]=f[i-1]*(g[i-1]+1)%p;
for(int i=60;~i;--i){
if((1ll<<i)<=m){
m-=(1ll<<i);
ans=(ans+res*f[i]%p)%p;
res=res*g[i]%p;
}
}
return (ans+1)*start%p;
}
int main(){
freopen("animism.in","r",stdin);
freopen("animism.out","w",stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin>>n>>k>>p;
for(int i=0;i<k;++i){
std::cin>>a[i];
a[i+k]=a[i];
}
k*=2,b[0]=1;
ll tmp=0;
bool sign=n&1;
if(!sign)tmp=1;
for(int i=1;i<k;++i){
b[i]=b[i-1]*a[i-1]%p;
if((i&1)==sign)tmp=(tmp+b[i])%p;
}
b[k]=b[k-1]*a[k-1]%p;
ll ans=solve(tmp,b[k],n/k-1),now=qpow(b[k],n/k);
for(ll i=n-n%k;i<=n;++i)if((i&1)==sign)ans=(ans+now*b[i%k]%p)%p;
std::cout<<ans;
return 0;
}