常系数线性递推

前置知识

多项式除法|取模

特征值与特征向量

（这部分我也不怎么理解，就大概记个结论）

对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $λ$ 满足
$A \vec{v} = λ \vec{v}$
移项则有 $(λ I - A) \vec{v} = 0$ ，其中 $I$ 为单位矩阵

那么有解的充要条件是 $d e t (λ I - A) = 0$

令 $f (λ) = d e t (λ I - A)$ ，即此时可将 $d e t (λ I - A)$ 看作一个 $n$ 阶多项式，则称 $f (λ)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$ ，其任意特征值 $λ_{0}$ 都满足 $f (λ_{0}) = 0$

$Hamiton-Cayley$ 定理

对矩阵 $A$ 及其特征多项式 $f (x)$ ，满足 $f (A) = O$ ，其中 $O$ 为零矩阵

证明留坑

常系数齐次线性递推

求一个满足 $k$ 阶齐次线性递推数列 $h_{i}$ 的第 $n$ 项，即
$h_{n} = \sum_{i = 1}^{k} f_{i} \times h_{n - i}$
它有三个特点

常系数：递推系数与下标无关
齐次：递推式不存在常数项，就类似 $y = a x + b$ 中 $b = 0$
线性：都为一次项

矩阵快速幂

加速矩阵 $A$ $\times$ 初始矩阵 $H$ ：
$(\begin{matrix} f_{1} & f_{2} & f_{3} & \dots & f_{n} \\ 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & \dots & ⋮ \\ 0 & 0 & 0 & \dots & 1 \end{matrix}) \times (\begin{matrix} h_{k} \\ ⋮ \\ h_{3} \\ h_{2} \\ h_{1} \end{matrix}) = (\begin{matrix} h_{k + 1} \\ ⋮ \\ h_{4} \\ h_{3} \\ h_{2} \end{matrix})$
那么快速幂 $A^{n} H$ 即可，复杂度 $O (k^{3} \log n)$

优化

考虑 $A \vec{v} = λ \vec{v}$ ，也就是说现在存在
$(\begin{matrix} h_{k + 1} \\ ⋮ \\ h_{4} \\ h_{3} \\ h_{2} \end{matrix}) = (\begin{matrix} λ h_{k} \\ ⋮ \\ λ h_{3} \\ λ h_{2} \\ λ h_{1} \end{matrix})$
推广一下， $h_{n} = λ^{n - 1} h_{1}$ ，则
$\begin{aligned} h_{k + 1} & = f_{1} h_{k - 1} + f_{2} h_{k - 2} + \dots + f_{k} h_{1} \\ λ^{k} h_{1} & = f_{1} λ^{k - 1} h_{1} + f_{2} λ^{k - 2} h_{2} + \dots + f_{k} h_{1} \\ λ^{k} & = f_{1} λ^{k - 1} + f_{2} λ^{k - 2} + \dots + f_{k} \end{aligned}$
将 $λ$ 替换为 $x$ ，则有 $F (x) = x^{k} - f_{1} x^{k - 1} - f_{2} x^{k - 2} - \dots - f_{k}$

此时 $F (x)$ 就是矩阵 $A$ 的特征多项式，有 $F (A) = 0$

考虑等式
$x^{n} = F (x) Q (x) + R (x)$
以 $A$ 代入，则有
$A^{n} = R (A)$
别忘了现在要求的是 $A^{n} \vec{v}$ ，那么两边同乘 $\vec{v}$ ，有 $A^{n} \vec{v} = R (A) \vec{v}$

$R (x)$ 可以通过由 $A (x) = x^{n}$ 对 $F (x)$ 取模求得，注意此时不能直接取模，因为 $n$ 可以非常大（比如 $n = 1 e 9 ）$ ，无法存下多项式 $x^{n}$ ，需要通过快速幂求解

设 $R (x) = \sum_{i = 0}^{k - 1} c_{i} x^{i}$ ，则
$A^{n} \vec{v} = \sum_{i = 0}^{k - 1} c_{i} A^{i} \vec{v}$
而 $A^{i} \vec{v}$ 实际上就是
$(\begin{matrix} h_{k + i} \\ ⋮ \\ h_{i + 3} \\ h_{i + 2} \\ h_{i + 1} \end{matrix})$
$A$ 的次数最多 $k - 1$ ，也就是说最多只会取到前 $2 k - 1$ 个 $h_{i}$ ，我们最后要取得是 $A^{n} \vec{v}$ 的第一位，每次乘上一个 $A$ 则令 $h$ 数组向下移一位，那么最终答案即为 $a n s = \sum_{i = 0}^{k - 1} c_{i} h_{i}$

时间复杂度 $O (k \log k \log n)$

其实每次在求多项式取模的时候都是对 $F (x)$ 取模，所以可以提前对 $F (x)$ 预处理，求出其逆，那么可以少很多常数（虽然我的常数还是贼大就是了。。）

cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MOD 998244353
#define g 3

using namespace std;

typedef long long LL;

const int MAXK = 32000 + 10;
const int MAXN = 1 << 20;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}
const LL invg = power (g, MOD - 2);

int oppo[MAXN]= {0}, limit;
void NTT (LL* a, int inv) {
	for (int i = 0; i < limit; i ++)
		if (i < oppo[i])
			swap (a[i], a[oppo[i]]);
	for (int mid = 1; mid < limit; mid <<= 1) {
		LL ome = power (inv == 1 ? g : invg, (MOD - 1) / (mid << 1));
		for (int n = mid << 1, j = 0; j < limit; j += n) {
			LL x = 1;
			for (int k = 0; k < mid; k ++, x = x * ome % MOD) {
				LL a1 = a[j + k], xa2 = x * a[j + mid + k] % MOD;
				a[j + k] = (a1 + xa2) % MOD;
				a[j + mid + k] = (a1 - xa2 + MOD) % MOD;
			}
		}
	}
}
LL A[MAXN], B[MAXN], O[MAXN]= {0};
void mul (LL* X, LL* Y, int fn, int fm, int rst) {
	int n, lim;
	for (n = 1, lim = 0; n <= fn + fm; n <<= 1, lim ++);
	limit = n;
	for (int i = 0; i < limit; i ++) oppo[i] = (oppo[i >> 1] >> 1) | ((i & 1) << (lim - 1));
	for (int i = 0; i < limit; i ++) A[i] = B[i] = 0;
	for (int i = 0; i <= fn; i ++) A[i] = X[i];
	for (int i = 0; i <= fm; i ++) B[i] = Y[i];
	NTT (A, 1), NTT (B, 1);
	for (int i = 0; i < limit; i ++) A[i] = A[i] * B[i] % MOD;
	NTT (A, - 1);
	LL invn = power (n, MOD - 2);
	for (int i = 0; i <= rst; i ++) X[i] = A[i] * invn % MOD;
	for (int i = rst + 1; i <= fn + fm; i ++) X[i] = 0;
}
void inverse (int deg, LL* a) {
	if (deg == 1) { a[0] = power (O[0], MOD - 2); return ; }
	inverse ((deg + 1) >> 1, a);
	int n, lim;
	for (n = 1, lim = 0; n <= deg << 1; n <<= 1, lim ++);
	limit = n;
	for (int i = 0; i < limit; i ++) oppo[i] = (oppo[i >> 1] >> 1) | ((i & 1) << (lim - 1));
	for (int i = 0; i < limit; i ++) A[i] = B[i] = 0;
	for (int i = 0; i < deg; i ++) A[i] = O[i];
	for (int i = 0; i < deg << 1; i ++) B[i] = a[i];
	NTT (A, 1), NTT (B, 1);
	for (int i = 0; i < limit; i ++) B[i] = B[i] * ((2ll - A[i] * B[i] % MOD + MOD) % MOD) % MOD;
	NTT (B, - 1);
	LL invn = power (n, MOD - 2);
	for (int i = 0; i < deg; i ++) a[i] = B[i] * invn % MOD;
}
LL R[MAXN], INVG[MAXN]= {0};
void prep (LL* G, int n, int m) {
	for (int i = 0; i <= m; i ++) O[i] = G[i];
	reverse (O, O + m + 1);
	for (int i = n - m + 2; i <= m; i ++) O[i] = 0;
	inverse (n - m + 1, INVG);
}
void PolyMod (LL* F, LL* G, int n, int m){ // F mod G = R
	for (int i = 0; i <= n; i ++) R[i] = F[i];
	reverse (R, R + n + 1); mul (R, INVG, n, n - m + 1, n);
	reverse (R, R + n - m + 1);
	for (int i = n - m + 1; i <= n; i ++) R[i] = 0;
	mul (R, G, n - m, m, n);
	for (int i = 0; i < m; i ++) R[i] = (F[i] - R[i] + MOD) % MOD;
	for (int i = 0; i <= n; i ++) { F[i] = i < m ? R[i] : 0; R[i] = 0; }
}

int N, K, L;
LL F[MAXK]= {0}, h[MAXK]= {0};

LL X[MAXN]= {0}, ANS[MAXN]= {0};
void PolyPow (int p) { // X ^ p (mod F)
	while (p) {
		if (p & 1) { mul (ANS, X, K - 1, K - 1, L); PolyMod (ANS, F, L, K); }
		mul (X, X, K - 1, K - 1, L); PolyMod (X, F, L, K);
		p >>= 1;
	}
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}

int main () {
	N = getnum (), K = getnum (); L = (K - 1) << 1;
	for (int i = 1; i <= K; i ++) F[K - i] = (MOD - getnum () % MOD) % MOD;
	for (int i = 0; i < K; i ++) h[i] = getnum () % MOD;
	F[K] = X[1] = ANS[0] = 1; prep (F, L, K);
	PolyPow (N);
	LL ans = 0;
	for (int i = 0; i < K; i ++) ans = (ans + ANS[i] * h[i] % MOD + MOD) % MOD;
	cout << ans << endl;

	return 0;
}

常系数非齐次线性递推

求一个满足 $k$ 阶齐次线性递推数列 $h_{i}$ 的第 $n$ 项，即
$h_{n} = P (n) + \sum_{i = 1}^{k} f_{i} \times h_{n - i}$