[CF1106F]Lunar New Year and a Recursive Sequence

本文主要是介绍[CF1106F]Lunar New Year and a Recursive Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lunar New Year and a Recursive Sequence

题解

~~忽的发现这题难度只有2400，还是我数学太菜了~~

如果像原式那样对整个式子每次都进行次方的更新的话，明显会T掉，我们可以对它的幂进行更新，因为做出贡献的项只有 $f_{k}$ 这一个，每个 $f_{i}$ 都可以只用 $f_{k}$ 表示出来。

设 $f_{i}$ 为 $f_{k}$ 的 $p_{i}$ 次方，可得 $p_{i}=\sum_{j=1}^{k}b_{j}\cdot p_{i-j}$ ，可如果暴力转移的话 $10^9$ 级别的 $n$ 明显会让我们T掉。

发现这个式子很容易用矩阵乘法实现转换，矩阵乘法就可以被定义为

$A=\begin{bmatrix} 0 &0 & \cdots & 0 &b_{k} \\ 1 & 0 &\cdots &0 & b_{k-1} \\ 0 & 1 & \cdots &0 &b_{k-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 &\cdots & 1 & b_{1} \end{bmatrix} , S= \begin{bmatrix} 0 & 0 & \cdots & 0 & 1 \end{bmatrix}$

由 $A$ 与 $S$ 两矩阵相乘来进行转换。

这样来进行转换。这样，第n项的指数就是 $S \times A^{n-1}$ 时的第 $1$ 项了。

因为这是求的次数，所以必须模 $998244353$ 。

由于 $a^{x}\equiv b (mod \: 998244353)$ 。由于 $998244353$ 的原根为 $3$ ，所以肯定有 $a\equiv 3^c (mod \: 998244353)$ 。

原式也可以被表示为 $3^{cx} \equiv b (mod \: 998244353)$ 。

接下来我们可以用BSGS求出 $cx\: mod\: 998244352$ 的值，用乘法逆元将这个 $x$ 消去，就可以得到 $c$ 的取值。答案即为 $3^{c}$ 。

于是就可以用 $O\left(k^{3}log_{n} \right )$ 的时间复杂度求出答案了。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
#define int LL
#define MAXN 500005
const double eps=1e-7;
const int INF=0x7f7f7f7f; 
const LL mo=998244353;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int qkpow(int a,int s){int t=1;while(s){if(s&1)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1;}return t;
}
int add(int x,int y){return x+y>=mo-1?x+y-mo+1:x+y;}
int K;
struct matrix{int c[105][105];matrix(){memset(c,0,sizeof(c));}friend matrix operator * (const matrix &a,const matrix &b){matrix res;for(int i=1;i<=K;i++)for(int k=1;k<=K;k++)if(a.c[i][k])for(int j=1;j<=K;j++) res.c[i][j]=add(res.c[i][j],1ll*a.c[i][k]*b.c[k][j]%(mo-1));return res;}
}A,B,C;
matrix mat_qkpow(matrix a,int s){matrix t;for(int i=1;i<=K;i++)t.c[i][i]=1;while(s){if(s&1)t=a*t;a=a*a;s>>=1;} return t;
}
map<int,int>mp;
int bsgs(LL p,int b,int n){int tmp=1,sum=1,m=ceil(sqrt(p));mp[n%p]=0;for(int i=1;i<=m;i++)tmp=1ll*tmp*b%p,mp[1ll*tmp*n%p]=i;for(int j=1;j<=m;j++){sum=1ll*sum*tmp%p;if(mp[sum])return j*m-mp[sum];}return -1;
}
int exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return a;}int d=exgcd(b,a%b,y,x);y-=x*(a/b);return d;
}
signed main(){read(K);A.c[1][K]=1;for(int i=K;i>0;i--)read(B.c[i][K]);for(int i=2;i<=K;i++)B.c[i][i-1]=1;int n,m;read(n);read(m);C=A*mat_qkpow(B,n-1);int t=bsgs(mo,3,m);if(t==-1){puts("-1");return 0;}int x,y,d=exgcd(C.c[1][1],mo-1,x,y);if(t%d){puts("-1");return 0;}x=(t/d*x%(mo-1)+mo-1)%(mo-1);printf("%lld\n",qkpow(3,x));return 0;
}