题目链接：CF1106F Lunar New Year and a Recursive Sequence
大意：已知\(f_1,f_2,\cdots,f_{k-1}\)和\(b_1,b_2,\cdots,b_k\)，且有递推关系
\[f_i=（\prod_{j=1}^kf_{i-j}^{b_j}）\text%p
\]
\]
对于所有\(i>k\)均成立，给出\(f_n=m\)，求\(f_k\)，\(p=998244353\)
分析：
数论板子大集合
首先很显然有\(f_n=f_k^{q}\)，于是考虑先求出这个\(q\)
看到\(k\leq100\)一般就会想到矩阵乘法之类的
但是这个式子的\(b\)处在乘方的位置，无法直接使用矩阵
注意到模数为998244353，其原根为3
那么我们就可以使用原根来改写这个转移
\[g_i=\prod_{j=1}^kg_{i-j}b_j
\]
\]
这个是可以利用矩阵乘法的，初值\(g_i=0(i<k),g_k=1\)
我们于是可以利用矩乘找到这样的关系式：\(f_k^{q}\equiv f_n(mod\ p),q=g_n\)
这个玩意似乎可以类比的被定义为k次剩余，不过我们显然不会这个玩意
于是我们继续使用原根
我们知道\(f_n\)可以被写作\(3^t\)，那么我们设\(f_k\)可以被写作为\(3^x\)
那么我们就是求满足这个式子的x值：\(3^{xq}\equiv3^t(mod\ p)\)
那么对于指数我们可以直接用exgcd，因为此时有\(xq\equiv t(mod\ p-1)\)
将m转为\(3^t\)时可以使用BSGS
问题就得到了解决QAQ
注意模数会在\(p-1\)和\(p\)之间切换，指数的模数为\(p-1\)（包括上面的矩乘），而在BSGS中的模数则为\(p\)
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define int long long
const int maxd=998244353,N=100000;
const double pi=acos(-1.0);
typedef long long ll;
int n,K,b[120],m;
struct matrix{
ll x[120][120];
}ans,sum;
matrix operator *(matrix a,matrix b)
{
matrix c;
memset(c.x,0,sizeof(c.x));
int i,j,k;
for (i=0;i<K;i++)
{
for (j=0;j<K;j++)
{
for (k=0;k<K;k++)
{
c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%(maxd-1);
}
}
}
return c;
}
void qpow(int tim)
{
while (tim)
{
int tmp=tim&1;tim/=2;
if (tmp) ans=ans*sum;
sum=sum*sum;
}
}
ll qpow(ll x,ll y)
{
ll ans=1,sum=x;
while (y)
{
int tmp=y&1;y/=2;
if (tmp) ans=(ans*sum)%maxd;
sum=(sum*sum)%maxd;
}
return ans;
}
map<ll,ll> mp;
ll bsgs(int a,int b)
{
int siz=sqrt(maxd-1)+1,i;ll sum=b;
for (i=0;i<=siz;i++)
{
mp[sum]=i;
sum=(sum*a)%maxd;
}
ll tmp=qpow(a,siz);sum=1;
for (i=1;i<=siz;i++)
{
sum=(sum*tmp)%maxd;
if (mp[sum]) return i*siz-mp[sum];
}
}
ll gcd(ll x,ll y)
{
if (!y) return x; else return gcd(y,x%y);
}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if (!b) {x=1;y=0;g=a;return;}
else
{
ll tmpx,tmpy;
exgcd(b,a%b,g,tmpx,tmpy);
x=tmpy;y=tmpx-a/b*tmpy;
}
}
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
signed main()
{
K=read();
int i,j;
for (i=0;i<K;i++) {ans.x[i][i]=1;sum.x[0][i]=read();}
for (i=0;i<K-1;i++) sum.x[i+1][i]=1;
ans.x[0][0]=1;
n=read();m=read();
qpow(n-K);
ll q=ans.x[0][0],p=bsgs(3,m);
//cout << q << " " << p << endl;
ll tmp=gcd(q,maxd-1);
if (p%tmp) {printf("-1");return 0;}
ll x,y,g;
exgcd(q,maxd-1,g,x,y);
x=(p/g*x)%(maxd-1);
if (x<0) x+=(maxd-1);
printf("%lld",qpow(3,x));
return 0;
}
/*
3
2 3 5
4 16
*/