题意理解

已知： $\sum_{k=0}^n a_k x^k = \sum_{k=0}^n b_k (x - t)^k$ 其中 $a_k$ 由递推式给出： $a_k = \begin{cases} (1234 \cdot a_{k - 1} + 5678) \bmod 3389 & k > 0 \\ 1 & k = 0 \end{cases} ​$ 输入 $n$, $t$, $m$（$n$ 很大，$n-m \le 5$），求 $b_m$。

关键思路

1. 公式转换

由二项式定理： $x^k = \sum_{i=0}^k \binom{k}{i} t^{k-i} (x-t)^i$ 代入左边： $\sum_{k=0}^n a_k \sum_{i=0}^k \binom{k}{i} t^{k-i} (x-t)^i = \sum_{i=0}^n \left( \sum_{k=i}^n a_k \binom{k}{i} t^{k-i} \right) (x-t)^i$ 因此： $b_i = \sum_{k=i}^n a_k \binom{k}{i} t^{k-i}$

2. 问题简化

题目中 $n$ 很大（可达 $10^{3000}$），但 $n-m \le 5$，所以 $m$ 接近 $n$，$b_m$ 只与 $a_k$ 中 $k \ge m$ 的项有关： $b_m = \sum_{k=m}^n a_k \binom{k}{m} t^{k-m}$ 因为 $n-m \le 5$，所以求和项数不超过 $6$。

3. 大数处理

$n$, $m$ 用字符串读入，用高精度类 $Mint$ 存储（每 $9$ 位十进制数压成一位）。

递推式 $a_k$ 模 $3389$，且是周期序列（周期 $len$ 可预处理）。

计算 $a_k$ 时，由于 $k$ 很大，利用周期性：$a_k = a_{k \bmod len}$。

4. 组合数计算

需要计算 $\binom{k}{m}$，其中 $k$ 从 $m$ 到 $n$，$n-m \le 5$。 $\binom{k}{m} = \frac{k(k-1)\cdots(k-m+1)}{m!}$ 由于 $m$ 不大，可以直接计算。

算法步骤

1.预处理周期：计算 $a_k$ 序列的周期 $len$。

2.读入大数：将 $n$, $m$ 读入高精度类。

3.计算 $c = n-m$：由于 $c \le 5$，只需计算 $k = m, m+1, \dots, n$ 的项。

4.计算每项： $term_k = a_k \cdot \binom{k}{m} \cdot t^{k-m}$ 其中：

$a_k = a_{(m + i) \bmod len}$（$i$ 从 $0$ 到 $c$）

$\binom{k}{m} = \frac{\prod_{j=0}^{m-1} (k-j)}{m!}$

$t^{k-m}$ 直接计算

5.求和：$b_m = \sum_{k=m}^n term_k$

代码关键点

$Mint$ 类实现高精度的加、乘、除。

利用周期性避免计算巨大的 $k$ 对应的 $a_k$。

由于 $n-m$ 很小，直接循环计算这几项。

总结

本题结合了：

生成函数与二项式定理

模运算周期性

高精度计算

组合数公式

关键观察是 $n-m \le 5$ 极大简化了计算，只需计算少数几项。