「2020 省选联考 A 卷 D1T2」组合数问题

从现在开始我 blog 写题解要附上简要题意（

给定 $m$ 次多项式 $F(x)=\sum_{i=0}^{m}f_{i}x^{i}$，试求

$$\sum_{k=0}^{n}{n\choose k}F(k)x^{k}\$$

在 $\operatorname{mod}p$ 意义下的值。

其中 $1\leqslant n,x,p\leqslant 10^{9},0\leqslant f_{i}\leqslant 10^{9},1\leqslant m\leqslant\min(n,1000)$。

不过话说回来，D2 早上去机房听烜说这是道衡水的原题，而且还是比原题简单的那种。

首先我们把 $F(k)$ 拆开，得到

$$\sum_{i=0}^{m}f_{i}\sum_{k=0}^{n}{n\choose k}k^{i}x^{k}$$

考虑到 $m$ 比较小，我们可以对于外层 $\sum$ 的每一项单独求值。定义

$$\begin{aligned} G_{n,t}(x)&=\sum_{k=0}^{n}{n\choose k}k^{t}x^{k}\\ &=\sum_{k=0}^{n}\left({n-1\choose k}+{n-1\choose k-1}\right)k^{t}x^{k}\\ &=\sum_{k=0}^{n}{n-1\choose k}k^{t}x^{k}+\sum_{k=0}^{n}{n-1\choose k-1}k^{t}x^{k}\\ &=\sum_{k=0}^{n-1}{n-1\choose k}k^{t}x^{k}+\sum_{k=0}^{n-1}{n-1\choose k}(k+1)^{t}x^{k+1}\\ &=\sum_{k=0}^{n-1}{n-1\choose k}k^{t}x^{k}+x\sum_{i=0}^{t}{t\choose i}\sum_{k=0}^{n-1}{n-1\choose k}k^{t}x^{k}\\ &=G_{n-1,t}(x)+x\sum_{i=0}^{t}{t\choose i}G_{n-1,i}(x) \end{aligned}$$

于是我们构造矩阵

$$A=\begin{bmatrix} {0\choose 0}x+1&0&0&\cdots&0&0&1\\ {1\choose 0}x&{1\choose 1}x+1&0&\cdots&0&0&0\\ {2\choose 0}x&{2\choose 1}x&{2\choose 2}x+1&\cdots&0&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ {m-1\choose 0}x&{m-1\choose 1}x+1&{m-1\choose 2}x&\cdots&{m-1\choose m-1}x+1&0&0\\ {m\choose 0}x&{m\choose 1}x&{m\choose 2}x&\cdots&{m\choose m-1}x&{m\choose m}x+1&0\\ 0&0&0&\cdots&0&0&1 \end{bmatrix}$$

和初始向量

$$S=\begin{bmatrix} 1\\ 0\\ 0\\ \vdots\\ 0\\ 0\\ 1 \end{bmatrix}$$

那么

$$A^{n}S=\begin{bmatrix} G_{n,0}(x)\\ G_{n,1}(x)\\ G_{n,2}(x)\\ \vdots\\ G_{n,m-1}(x)\\ G_{n,m}(x)\\ 1 \end{bmatrix}$$

虽然我在我的另一个 blog 里写过了，不过由于某些原因那个 blog 倒了，于是我在这里再写一遍。

如果直接使用矩阵快速幂来计算 $A^{n}$ 的话，复杂度是 $O(m^{3}\log n)$ 的，但是这还不够。

考虑我们能不能构造出一个奇妙的序列 $c_{0},c_{1},\cdots,c_{m+1}$ 使得 $C(A)=\sum_{i=0}^{m+1}c_{i}A^{i}=A^{n}$。

如果我们构造出来了，令 $S_{k}$ 表示 $S$ 从上往下第 $k$ 维的值，从 $0$ 开始标号。那么

$$(A^{n}S)_{k}=\left(\sum_{i=0}^{m+1}c_{i}A^{i}S\right)_{k}=\sum_{i=0}^{m+1}c_{i}(A^{i}S)_{k}$$

注意到 $(A^{i}S)_{k}$ 就是 $G_{i,k}(x)$，不过如果 $k=m+1$ 就是 $1$。这样我们就可以在 $O(m^{2})$ 的复杂度内计算出答案。

我们设 $A^{n}=P(A)Q(A)+C(A)$，如果我们能够找到一个 $m+2$ 次多项式 $H$ 使得 $Q(A)=0$，就可以有 $C(A)=A^{n}\operatorname{mod}Q(A)$。

一下是一些为了求出 $H$ 所必要的矩阵相关知识。

对于矩阵 $A$，如果等式 $(\lambda I-A)v=0$ 成立，我们称 $\lambda$ 是 $A$ 的一个特征值，$v$ 是 $A$ 的一组特征向量。

有两个连 shadowice dalao 都不会证的结论：

1. 满足 $\text{Det}(A)\neq 0$，即满秩的 $n\times n$ 的矩阵 $A$ 拥有 $n$ 组线性无关的特征向量。
2. 当且仅当 $\text{Det}(\lambda I-A)=0$ 时存在这样的 $v$。

显然我们刚才构造的矩阵 $A$ 是满秩的。于是根据 Cayley-Hamilton 定理，有 $\prod_{k=0}^{m+1}(\lambda_{k}I-A)=0$，其中 $\lambda_{0},\lambda_{1},\cdots,\lambda_{m+1}$ 表示 $A$ 的 $m+2$ 组特征向量。

于是 $Q(A)=\prod_{k=0}^{m+1}(\lambda_{k}I-A)$。

考虑另外一个多项式 $R(\lambda)=\text{Det}(\lambda I-A)$，根据 shadowice dalao 的 blog，这两个多项式的系数对应相等。

而显然 $\text{Det}(\lambda I-A)=(\lambda-1)(\lambda-x-1)^{m+1}$，使用分治 NTT 可以在 $O(m\log^{2}m)$ 的复杂度内计算出来。

那么总结一下：

1. 计算 $R(\lambda)=\text{Det}(\lambda I-A)=(\lambda-1)(\lambda-x-1)^{m+1}$，复杂度 $O(m\log^{2}m)$。
2. 设 $R(\lambda)=\sum_{i=0}^{m+2}q_{i}\lambda^{i}$，有 $Q(A)=\sum_{i=0}^{m+2}q_{i}A^{i}=0$。
3. 计算 $C(A)=A^{n}\operatorname{mod}Q(A)$，时间复杂度 $O(m\log m\log n)$。
4. 设 $C(A)=\sum_{i=0}^{m+1}c_{i}A^{i}$，有 $(A^{n}S)_{k}=\sum_{i=0}^{m+1}c_{i}(A^{i}S)_{k}$，也即 $G_{n,k}(x)=\sum_{i=0}^{m+1}c_{i}G_{i,k}(x)$。
5. 对于所有的 $0\leqslant i\leqslant m+1,0\leqslant k\leqslant m$ 计算 $G_{i,k}(x)$，我们发现 $G$ 的暴力递推式可以转化成 EGF，于是做 $m$ 遍卷积，复杂度 $O(m^{2}\log m)$。

那么总体的复杂度相当于 $O(m^{2}\log m)$。

然而我一点都不想写这个玩意（