分析一下题目，大致意思就是给定一组常数 \(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;
}