51nod 1360 K-序列

发表于 更新于 分类于

题目

有Q个查询，对于每一个查询q[i]，请计算S(q[i])%m。 拆一下第二个函数 \[S((\lfloor\frac{n}{k}\rfloor-1)*k+i)=S((n-k)-n\%k+i)\]

可以发现这个式子按\(\mod k\)余数分类后，可以用矩阵乘法来做。

以下来自题解

可以先把数据分块，每K个一块，后一块和前一块之间的关系可以用矩阵来表示。

这个矩阵太大了。直接做矩阵乘法肯定会超时。但是这个矩阵有一个特殊性，使得它的乘法有优化的空间。

C是一个常数，先预处理，那么就可以在log(qi)的时候内计算出S(qi)的值了。

复杂度是预处理O(K),查询log(qi)