题解：P5808 【模板】常系数非齐次线性递推

考虑延用齐次时的做法。设

\mathbf{x}_n,\mathbf{y}_n

两个列向量为：

a_{n-k}\\ a_{n-k+1} \\ \vdots \\ a_{n-1}\\ a_n\\ \end{bmatrix},\mathbf{y}_n=\begin{bmatrix} n^m\\ n^{m-1} \\ \vdots \\ n\\ 1\\ \end{bmatrix}$$ 故我们要对 $\begin{bmatrix} \mathbf{x}_n\\ \mathbf{y}_n \end{bmatrix}$ 进行递推，容易发现转移矩阵形如 $\begin{bmatrix} A& B\\ O&C \end{bmatrix}$，其中 $O$ 为 $0$ 矩阵。即： $$\begin{bmatrix} \mathbf{x}_{n+1}\\ \mathbf{y}_{n+1} \end{bmatrix}=\begin{bmatrix} A& B\\ O&C \end{bmatrix}\begin{bmatrix} \mathbf{x}_n\\ \mathbf{y}_n \end{bmatrix}=\begin{bmatrix} A\mathbf{x}_n+B\mathbf{y}_n\\ C\mathbf{y}_n \end{bmatrix}$$ 容易依题意列出 $A,B$，同时依二项式定理可以列出 $C$，会发现 $C$ 是一个主对角线全 $1$（$\binom{n}{n}=1$）的上三角矩阵，因为我们是用低次来线性组合出高次。考虑这东西的特征多项式，显然是 $p_A(\lambda)p_C(\lambda)$，依次沿最后一行展开易证。也即 $(\lambda^k-\sum_{i=0}^{k-1}f_{k-i+1}\lambda^i)(1-\lambda)^{m+1}$。这是一个 $m+k+1$ 次多项式，我们需要求出前 $m+k+1$ 项，才能套用齐次的做法。 可以多项式多点求值以后参照[【模板】分治 FFT](https://www.luogu.com.cn/problem/P4721)，快速求出前 $m+k+1$ 项，可以通过这道题。 然而，现在是 $2025$ 年，由于出题人很良心，所以我们暴力求前 $m+k+1$ 项（大概率）也可以通过这个题，参照 [暴力过多点求值](https://www.luogu.com.cn/article/kitad12w)。毫无疑问，本题数据范围远远弱于多点求值，很可能可以通过。 遗憾的是，笔者的多项式板子过于烂，导致取模时就已经超时，而笔者忙于学业，无暇改进多项式板子并实现暴力卡常做法。下面给出并不能通过的主函数，来进一步阐释上文。[记录](https://www.luogu.com.cn/record/201006618)。 ```cpp int main(){ int n,m,K; cin>>n>>m>>K;++m; poly f(K),p(m),a(K+m); for(int i=0;i<K;++i)cin>>a[i]; for(auto &x:f)cin>>x; for(auto &x:p)cin>>x; poly A=f,B(m+1); reverse(A.begin(),A.end()); A.push_back(P-1); B[0]=1; for(int i=1;i<=m;++i)B[i]=B[i-1]*fp(i)%P*(P-1)%P*(m-i+1)%P; A=A*B; poly now={0,1},cf={1}; for(;n;n>>=1,now=now*now%A) if(n&1)cf=cf*now%A; for(int j=K;j<K+m;++j){ ll sum=calc(p,j);//求多项式 p 在 j 处的点值 for(int i=1;i<=K;++i) sum=(sum+f[i-1]*a[j-i])%P; a[j]=sum; } ll ans=0; for(int i=0;i<m+K;++i)ans=(ans+cf[i]*a[i])%P; printf("%lld\n",ans); return 0; } ```

题解：P5808 【模板】常系数非齐次线性递推

文章操作

相关推荐

评论

题解：P5808 【模板】常系数非齐次线性递推