题解：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 矩阵。即：

\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，快速求出前 m+k+1 项，可以通过这道题。

然而，现在是 2025 年，由于出题人很良心，所以我们暴力求前 m+k+1 项（大概率）也可以通过这个题，参照 暴力过多点求值。毫无疑问，本题数据范围远远弱于多点求值，很可能可以通过。

遗憾的是，笔者的多项式板子过于烂，导致取模时就已经超时，而笔者忙于学业，无暇改进多项式板子并实现暴力卡常做法。下面给出并不能通过的主函数，来进一步阐释上文。记录。

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;
}