题解：礼物数列快速计算

问题转化

设第 $i$ 个朋友送的礼物数为 $a_i$，根据题意有：

$$a_1 = 1$$ $$a_{n+1} = \sum_{i=1}^{n} a_i + (n+1)^K \quad (n \ge 1) $$

关键推导

1. 简化递推

令 $S_n = \sum_{i=1}^{n} a_i$，则 $a_{n+1} = S_n + (n+1)^K$，且 $S_{n+1} = S_n + a_{n+1}$。

代入得：

$$a_{n+1} = S_n + (n+1)^K$$ $$S_{n+1} = S_n + [S_n + (n+1)^K] = 2S_n + (n+1)^K$$

2. 建立矩阵递推

设状态向量为：

$$X_n = \begin{bmatrix} S_n \\ n^K \\ n^{K-1} \\ \vdots \\ n^1 \\ 1 \end{bmatrix} $$

需要将 $X_n$ 递推到 $X_{n+1}$。

多项式降幂关系

$(n+1)^t = \sum_{j=0}^{t} \binom{t}{j} n^j$

对于 $t=0,1,\dots,K$ 有：

$$(n+1)^t = \sum_{j=0}^{t} C(t,j) \cdot n^j$$

其中 $C(t,j) = \binom{t}{j}$。

$S$ 的递推

$$S_{n+1} = 2S_n + (n+1)^K = 2S_n + \sum_{j=0}^{K} C(K,j) n^j $$

构造转移矩阵

矩阵大小：$(K+2) \times (K+2)$。

第一行对应 $S$：

• $S$ 的系数：$2$
• $n^j$ 的系数：$C(K,j)$（其中 $0 \le j \le K$）

第 $i$ 行（$i\ge 2$）对应 $(n+1)^{K+2-i}$： 设 $t = K+2-i$，则：

$$(n+1)^t = \sum_{j=0}^{t} C(t,j) n^j$$

因此该行在 $n^j$ 列上的系数为 $C(t,j)$，其余为 $0$。

3. 矩阵形式

设 $M$ 为转移矩阵：

$$X_{n+1} = M \cdot X_n$$

具体形式：

$$M = \begin{bmatrix} 2 & C(K,K) & C(K,K-1) & \cdots & C(K,0) \\ 0 & C(K,K) & C(K,K-1) & \cdots & C(K,0) \\ 0 & 0 & C(K-1,K-1) & \cdots & C(K-1,0) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & C(0,0) \end{bmatrix} $$

更准确地说： $M_{1,1} = 2$， $M_{1,j} = C(K, K+2-j)$ 对于 $j\ge 2$， 对于 $i\ge 2$，$M_{i,j} = C(K+2-i, K+2-j)$ 当 $j \ge i$，否则为 $0$。

4. 求 $a_N$

因为 $a_N = S_N - S_{N-1}$，且 $S_N = [M^{N-1} X_1]_1$。

初始 $X_1$： $S_1 = a_1 = 1$， $1^K = 1, 1^{K-1}=1, \dots, 1^0=1$。

所以：

$$X_1 = [1, 1, 1, \dots, 1]^T$$

计算 $X_N = M^{N-1} X_1$，取第一个分量得 $S_N$， 计算 $X_{N-1} = M^{N-2} X_1$，取第一个分量得 $S_{N-1}$， 则 $a_N = S_N - S_{N-1}$。

5. 边界情况

$N=1$ 时直接输出 $1$。

6. 实现细节

• 模数 $MOD = 10^9+7$
• 矩阵大小 $m = K+2 \le 12$，矩阵乘法 $O(m^3)$
• 用快速幂计算 $M^{N-1}$，复杂度 $O(m^3 \log N)$
• 组合数预处理到 $K \le 10$ 即可

算法步骤

1. 读入 $N, K$
2. 若 $N=1$ 输出 $1$
3. 预处理组合数 $C[i][j]$ 模 $MOD$
4. 构造 $m \times m$ 转移矩阵 $M$
5. 计算 $X_1$（全 $1$ 向量）
6. 计算 $P = M^{N-1}$，$Q = M^{N-2}$（当 $N>1$）
7. 计算 $S_N = (P \cdot X_1)[0]$，$S_{N-1} = (Q \cdot X_1)[0]$
8. 输出 $(S_N - S_{N-1}) \bmod MOD$

复杂度分析

• 时间复杂度：$O((K+2)^3 \log N)$，完全满足 $N \le 10^{18}, K \le 10$
• 空间复杂度：$O((K+2)^2)$