居然没人写常系数齐次线性递推/jy
题意明确。
首先我们注意到这个系数是在幂上面的,这道题的各种信息都是建立在乘法上的,十分不好处理,考虑求一个 \(\ln\) 将这些信息建立在加法上。
\[\ln f[n]=\sum_{i=1}^kb[i]\ln f[n-i]
\]
可以发现这个问题变成了一般的常系数齐次线性递推。
然后发现 \(f_1 \sim f_{k-1}\) 在取了 \(\ln\) 之后全部都变成了 \(0\)。
考虑使用常系数齐次线性递推的老算法,因为老算法算的实际上是前 \(k\) 项对第 \(n\) 项的贡献。
所以跑一遍老算法就能够得到有 \(x \times \ln f[k] = \ln f[n]\),也就是 \(f[k]^x = f[n]\)。
于是只需要在模质数的意义下做 \(k\) 次剩余即可。
#include<unordered_map>
#include<cstdio>
typedef unsigned ui;
const ui M=205,MOD=119<<23,mod=MOD|1;
ui len,n,m,p[M];
inline ui pow(ui a,ui b=mod-2){
ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
inline ui Ln(const ui&x){
ui i,y;const ui X=3,Y=393213064,M=31596;std::unordered_map<ui,ui>hs;
if(hs.empty()){
for(y=1,i=1;i<=M&&(y=1ull*y*X%mod);++i)hs[y]=i;hs[1]=0;
}
for(y=1,i=1;i<=M&&(y=1ull*y*Y%mod);++i)if(hs.find(1ull*y*x%mod)!=hs.end())return(hs[1ull*y*x%mod]+i*M)%MOD;
return-1;
}
inline void times(ui*f,ui*g,ui*P,const ui&len){
ui i,j,t;static ui sav[M];
for(i=0;i^len;++i)if(f[i])for(j=0;j^len;++j)if(g[j])sav[i+j]=(sav[i+j]+1ull*f[i]*g[j])%MOD;
for(i=len*2-1;i>=len;--i)if(sav[i])for(t=sav[i],j=len;~j;--j)sav[i-j]=(sav[i-j]+1ull*t*P[j])%MOD;
for(i=0;i^len;++i)f[i]=sav[i],sav[i]=0;
}
inline ui Solve(ui*P,const ui&len,ui n){
static ui f[M],sav[M];if(len^1)f[1]=1;else f[0]=p[1];sav[0]=1;
for(;n;n>>=1,times(f,f,P,len))if(n&1)times(sav,f,P,len);return sav[len-1];
}
ui gcd(const ui&a,const ui&b){
return b?gcd(b,a%b):a;
}
void exgcd(int a,int b,int&x,int&y){
if(!b)return x=1,y=0,void();exgcd(b,a%b,y,x);y-=a/b*x;
}
signed main(){
ui i,ans(0);int a,b,x,y;scanf("%u",&len);p[0]=MOD-1;for(i=1;i<=len;++i)scanf("%u",p+i);scanf("%u%u",&n,&m);
if(n<len)return printf("-1"),0;
a=Solve(p,len,n-1);b=Ln(m);i=gcd(a,MOD);
if(b%i)return printf("-1"),0;a/=i;b/=i;exgcd(a,MOD/i,x,y);
printf("%u",pow(3,1ull*b*(x+MOD/i)%(MOD/i)));
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章