日志-2025-6

发表于 2025-06-10

Week 1

首先考虑暴力 DP ，记 $dp_{i,j,k}$ 为前 $i$ 个数，第 $i$ 个数加 $j$ ，操作次数为 $k$ 序列权值之和。

那么有：

dp_{i,j,k}= \sum _{x=1}^j dp_{i-1,x,k-(j-x)}+\sum_{x=j+1}^t dp_{i-1,x,k}

注意到一个状态是有效的，当且仅当 $j \le k$ ，所以对于每一个 $i$ ，真正有用的 $dp$ 值至多不会超过 $10$ 个。

于是我们就可以考虑把每个 $i$ 换成矩阵。

考虑这道题怎么做，对每个位置维护一个转移矩阵，然后使用线段树维护区间乘法就可以了。

时间复杂度： $O(nt^6+q \log n t^6)$ 。

发现会被卡掉，于是考虑优化。

在每次询问的时候，定义一个向量，然后用向量乘上线段树上的 $\log n$ 个区间即可。