本题最初始的设想

对于序列 $A_i$ 的任意 $k$ 个数字之和互不相等，但是通过暴力的方法计算出 $k=3$ 的序列为：

$1, 2, 3, 5, 8, 14, 25, 45, 82, 140 ...$

可以计算出：

该样例下无法进行递推，因此加入限制条件： 序列为 $S$ 的「交响」应当按照组合 $\delta$ 字典序增加的顺序从小到大演奏

递推公式证明

在组合 $K$ 下，对于序列 $A_i$ 前 $n$ 个数的最大组合为：

$$\begin{equation}\begin{split} sum(\delta_n + \delta_{n-1} + .. + \delta_{n-k+1})=\sum_{i=n-k+1}^{n}\delta_i \end{split}\end{equation}$$

加入第 $n+1$ 个数时最小组合为：

$$\begin{equation}\begin{split} sum(\delta_{n+1} + \delta_1 + .. + \delta_{k-1}) & =\delta_{n+1}+\sum_{i=1}^{k-1}\delta_i \\ & =\delta_{n+1}+C \end{split}\end{equation}$$

使 $(2)$ 刚好大于 $(1)$ 则有：

$$\begin{equation}\begin{split} & \delta_{n+1}+\sum_{i=1}^{k-1}\delta_i>\sum_{i=n-k+1}^{n}\delta_i\\\ \Rightarrow\quad & \delta_{n+1}+\sum_{i=1}^{k-1}\delta_i=\sum_{i=n-k+1}^{n}\delta_i+1\\\ \Rightarrow\quad & \delta_{n+1}=\sum_{i=n-k+1}^{n}\delta_i+1-\sum_{i=1}^{k-1}\delta_i\\\ \Rightarrow\quad & \delta_{n+1}=\sum_{i=n-k+1}^{n}\delta_i-\sum_{i=2}^{k-1}\delta_i\\\ \Rightarrow\quad & \delta_{n+1}=\sum_{i=n-k+1}^{n}\delta_i-C\\\ \end{split}\end{equation}$$

当然仍然存在一个问题，对于 $\forall K$ 应该如何确定 $A_1,...,A_n$ 的构造方法？

完备性证明

假设存在 $k$ 相关的函数 $n=f(k)$ 作为临界值

1. 公式 $(3)$ 需要在 $n=f(k)$ 之后的位置成立
2. $n=f(k)$ 之前的数需要满足任意的 $k-1$ 个数之和各不相同

令 $f(k) = 2k-1\\$ 任意选取组合，在 $C_{2k-1}^{k}$ 时，总会存在同一个元素重叠，去掉任意重叠的选取元素，在 $A_1,...,A_{2k-1}$ 中寻取 $K$ 组合问题退化为 $K-1$ 组合问题，满足要求

因此序列 $A$ 在 $K$ 下的递推定义为：

1. $A_1,...,A_{2k-1}$等价于 $k-1$ 下的序列
2. $n=2k$ 之后使用公式$(3)$递推

时间复杂度

先对 $k*(2k-1)$ 打表，采用一般递推方法时，时间复杂度为 $O(CK\delta_i)\approx 10^9$ $\quad$ 60分

使用矩阵快速幂 $O(CKlog\delta K^3)\approx 2*10^8$ $\quad$ 80分

优化访存命中，在矩阵乘法中将 $(i,j,k)\rightarrow(i,k,j)$ 矩阵乘法时间复杂度优化为原有 $\frac{1}{10}$

打表