题解

思路

令 $f_{i,j}$ 表示以位置 $i$ 结尾、长度恰好为 $j$ 的严格递增子序列个数。显然 $f_{i,1}=1$，且

直接枚举前驱需要 $O(kn^2)$。由于序列元素互不相同且都在 $1$ 到 $n$ 之间，可以对每个长度 $j$ 建立一棵树状数组：下标是末尾元素值，存储已经扫描过的位置产生的计数。

做法

从左到右扫描每个值 $a_i$。长度为 $1$ 的状态贡献为 $1$。对于 $j=2,3,\ldots,k+1$，查询第 $j-1$ 棵树状数组在值域 $[1,a_i-1]$ 的前缀和，得到 $f_{i,j}$，再把它加入第 $j$ 棵树状数组的坐标 $a_i$。最后查询第 $k+1$ 棵树状数组的全局和。

虽然最终答案保证不超过 $8\times10^{18}$，某些不会继续延伸的较短状态总数可能更大。所有计数均为非负数，因此可以把每次加法饱和到 $8\times10^{18}+1$：若一个被后续转移使用的和超过该值，最终答案也会超过保证；对合法输入的最终答案不会失真。

子任务 1 中目标长度为 $1$，每个位置各贡献一个答案。子任务 2 可直接按转移式枚举所有 $p<i$。

证明

任意一条以 $i$ 结尾、长度为 $j$ 的递增子序列，删去最后的 $a_i$ 后，会唯一得到一条以某个 $p<i$ 结尾、长度为 $j-1$ 且满足 $a_p<a_i$ 的递增子序列。反之，任意这样的较短子序列都能唯一接上 $a_i$。因此转移式没有遗漏也没有重复计数。

扫描到 $i$ 时，每棵树状数组只含位置小于 $i$ 的状态；查询值域 $[1,a_i-1]$ 又恰好筛出末尾值小于 $a_i$ 的状态。因此树状数组查询与转移式完全一致。由长度和扫描位置的归纳，所有状态计数正确，最后对所有结尾求和即得到所求答案。

复杂度

• 时间复杂度：$O(kn\log n)$。
• 空间复杂度：$O(kn)$。