分析一下题目，大致意思就是给定一组常数 \(a_i\)，然后有一个递推式 \(w_i=\sum _{j=1}^{n} w_{i-j}\times a_{j}\)，让你求出 \(w_m\) 对于 \(4147\) 取模的值。
根据这个 \(1\leq m\leq 10^7\) 的恐怖范围，姑且算到了 \(O(m)\) 的时间复杂度。但是观察一下这个递推式，发现 \(O(m)\) 跑不出来。于是乎我们自然就想到了使用矩阵快速幂优化。
我们先构造出初始矩阵：
\[st=
\left(
\begin{matrix}
w_n & w_{n-1} & \dots & w_2 & w_1
\end{matrix}
\right)
\]
接着我们需要将其进行转移，得到新的 \(w_{n+1}\) 的值，最后使用快速幂求出 \(w_{m}\) 的值。那么很明显，对于这个转移矩阵的第一列肯定是从 \(w_n\) 到 \(w_{n+1}\) 的所有常数 \(a_i\)，而后面的 \(n-1\) 项我们只需要直接赋值就可以了。整个式子差不多就是这个样子：
\[\left(
\begin{matrix}
w_{n+1} & w_{n} & \dots & w_3 & w_2
\end{matrix}
\right)
=
\left(
\begin{matrix}
w_n & w_{n-1} & \dots & w_2 & w_1
\end{matrix}
\right)
\times
\left(
\begin{matrix}
a_1 & 1 & 0 & \dots & 0 & 0 \\
a_2 & 0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & 0 & 0 & \dots & 1 & 0 \\
a_{n-1} & 0 & 0 & \dots & 0 & 1 \\
a_n & 0 & 0 & \dots & 0 & 0
\end{matrix}
\right)
\]
然后我们根据快速幂，把最后的矩阵直接算出来：
\[\left(
\begin{matrix}
w_m & w_{m-1} & \dots & w_{m-n+2} & w_{m-n+1}
\end{matrix}
\right)
=
\left(
\begin{matrix}
w_n & w_{n-1} & \dots & w_2 & w_1
\end{matrix}
\right)
\times
\left(
\begin{matrix}
a_1 & 1 & 0 & \dots & 0 & 0 \\
a_2 & 0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
a_{n-2} & 0 & 0 & \dots & 1 & 0 \\
a_{n-1} & 0 & 0 & \dots & 0 & 1 \\
a_n & 0 & 0 & \dots & 0 & 0
\end{matrix}
\right)
^{m-n+1}
\]
这样我们取这个矩阵的 \(w_m\) 输出来就可以了。
代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=4147;
const int MAXN=105;
int n,m;
int st[MAXN],a[MAXN];
int fr[MAXN][MAXN];
void mul(long long f[105],long long a[105][105])
{long long c[105];memset(c,0,sizeof(c));for(int j=0;j<n;j++){for(int k=0;k<n;k++) c[j]=(c[j]+(long long)f[k]*a[k][j])%MOD;}memcpy(f,c,sizeof(c));
}
void mulself(long long a[105][105])
{long long c[105][105];memset(c,0,sizeof(c));for(int i=0;i<n;i++){for(int j=0;j<n;j++){for(int k=0;k<n;k++) c[i][j]=(c[i][j]+(long long)a[i][k]*a[k][j])%MOD;}}memcpy(a,c,sizeof(c));
}
signed main()
{cin>>n>>m;for(int i=0;i<n;i++) cin>>st[n-i-1];for(int i=0;i<n;i++) cin>>a[i];for(int i=1;i<n;i++) fr[i][i-1]=1;for(int i=0;i<n;i++) fr[i][n-1]=a[n-i-1];int sum=m-n;while(sum){if(sum&1) mul(st,fr);sum>>=1;mulself(fr);}cout<<st[n-1];return 0;
}
