以下默认小写字母 \(\mathbf{a},\mathbf{b}\) 等表示的向量是一个行向量，\(\mathbf{1}\) 表示全 \(1\) 行向量，\(\operatorname{diag(\mathbf{a})}\) 表示一个大小 \(|\mathbf{a}|\times |\mathbf{a}|\) 的矩阵，满足 \((i,i)=a_i\) 且其余项为 \(0\)。
缘起：模拟赛题被AI爆标了，原因竟然是：
求 \(\mathbf{a}\times A^{t}\times \mathbf{b^T}\) 的值。
其中 \(A=\mathbf{1^T}\mathbf{c}+\operatorname{diag(d_0,d_1\dots d_{n-1})}\)。
这样特殊的矩阵需要用一些技术处理，下面先了解这些技术。
常系数齐次线性递推
目前只涉及求 \(n\) 阶齐次线性递推数列 \(f\) 的第 \(m\) 项。
一般我们需要解决这样的问题：
给定递推系数 \(g_1\sim g_{n}\) 以及初始项 \(f_0\sim f_{n-1}\)。
观察到这个样子很卷积啊：
建立 \(G(z)=1-\sum_{i=1}^nz^ig_i\)，或者说设 \(g'_0=1,g'_i=-g_i\)。
设 \(F(z)=\sum_{i=0}^{\infty}z^if_i\)。
我们要求 \([z^m]F(z)\)。
那么就有：
其中 \(R(z)=F(z)\times G(z)(\bmod x^n)\)，因为阶数 \(\ge n\) 的项都没了。
因此，做一次长度为 \(n\) 的多项式乘法就可以求出 \(R(z)\) 了，紧接着：
Bostan-Mori 算法求远处系数
正是求远处项系数，这是一个用递归理解的算法，每次规模减半。
那么按 \(m\) 的奇偶性保留 \(U_{even}\) 或者 \(U_{odd}\)，问题就只剩下全是平方项的多项式了，因此用 \(z^2\) 代替 \(z\)，问题规模就减半了。
最终剩下上下两个常数，直接算逆元就行。
我们每一轮只会有两次多项式乘法，效率非常高。
cin>>m>>n;vector<int>f(n+1),g(n+1);for(int i=1;i<=n;++i){cin>>f[i];f[i]=-f[i];}f[0]=1;for(int i=0;i<n;++i)cin>>g[i];g=Mul(f,g);while(g.size()>1&&(g.back()==0||g.size()>n))g.pop_back();while(m){//[x^m]g/fvector<int>h=f;for(int i=1;i<h.size();i+=2)h[i]=p-h[i];vector<int>nf=Mul(h,f),ng=Mul(g,h);f.clear();g.clear();for(int i=0;i<nf.size();i+=2)f.push_back(nf[i]); for(int i=(m&1);i<ng.size();i+=2)g.push_back(ng[i]);m>>=1;}cout<<g[0]*power(f[0],p-2)%p<<"\n";
矩阵快速幂与常系数齐次线性递推的转化
这是一个很重要的观察：若存在多项式 \(F(z)\)，满足 \(F(A)=0\)，那么我们称多项式 \(F\) 为矩阵 \(A\) 的零化多项式。
关于零化多项式的更多细节，[请移步](零化多项式 - spdarkle - 博客园)