CF1106F Lunar New Year and a Recursive Sequence

题目链接：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

*/