2020.08.14 yukicoder contest 261

2020.08.14 Educational Codeforces Round 93 (Rated for Div. 2)

比赛名称

比赛名称

Yukicoder P1172 - Add Recursive Sequence

• 题意：（方便起见，部分记法与原题不同）$a_0, a_1, \ldots, a_{\infty}$ 是一个 $k \leq 200$ 项常系数齐次线性递推数列，即对 $p \geq k$ 都有 $a_p = \sum _{i=1}^k a_{p-i} c_i$，且所需参数都已给定。现有一个长度为 $n \leq 10^5$ 的序列 $\{ x_n \}$，初始值都为 $0$，接着进行 $q$ 次操作，每次操作会选定一个区间 $[l, r]$，依次将该区间内对应的值加上 $a_0, a_1, \ldots, a_{r-l}$。求最后序列中每个位置的值模 $10^9 + 7$。

• 题解：首先考虑如何计算某个位置上 $x_i$ 的值。不妨假设所有区间端点都距离 $i$ 充分远，则 $x_i$ 也可以由它之前的 $k$ 项以 $c_1, c_2, \ldots, c_k$ 为系数递推得到（比较显然，相同递推的和式系数不变），因此可以维护一个 $f_i = x_i$，每次用 $f_{i-k}, f_{i-k+1} \ldots, f_{i-1}$ 推出 $x_i$，这部分的复杂度是 $O(nk)$ 的。

• 接着考虑区间端点距离 $i$ 并不充分远，使得 $x_i$ 中可能出现并没有递推关系的 $a_0, a_1, \ldots, a_{k-1}$ 的贡献（它们并不能通过递推得到）。我们可以先不将这一部分贡献加入 $f_i$，而是每次暴力将 $i$ 上 $a_0, a_1, \ldots, a_{k-1}$ 的贡献加入 $x_i$，然后只在某个区间准备对 $x_i$ 贡献 $a_k$ 这一项时，才给 $f_{i-k}, f_{i-k+1} \ldots, f_{i-1}$ 依次加上 $a_0, a_1, \ldots, a_{k-1}$，按之前提到的方法计算递推部分的贡献。这部分的复杂度是 $O((n + q)k)$ 的。

• 综上，总时间复杂度 $O((n + q)k)$。

• 备注：需要利用常系数齐次线性递推数列的性质，分开计算与维护 $<k$ 部分的贡献与 $\geq k$ 部分的贡献，还是比较巧妙的。

题目名称

• 题意：
• 题解：
• 备注：

题目名称

• 题意：
• 题解：
• 备注：