自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:09:51，当前版本为作者最后更新于2025-02-15 10:38:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意

有一个数列 $a_i$ 满足：

• 对于 $i\geq2$ 有 $25a_i+20a_{i-1}=12a_{i-2}$。
• $\forall i\in\mathbb{N},a_i\geq 0$。

给定一个长度为 $n$ 的序列 $a$，初始时全为 $0$，有 $m$ 次操作，支持：

• 1 l r x y $\forall i\in[l,r], a_i\gets a_{y+i-l}$，其中 $a_0=x$。保证 $a$ 序列通过既定条件可以唯一确定。
• 2 l r 求区间 $[l,r]$ 的和。答案对 $10^9+7$ 取模。

$1\leq n\leq 10^9,1\leq m\leq 10^5$。空间限制 $64\mathrm{MiB}$。

思路

先来解递推式。

对于 $25a_i+20a_{i-1}=12a_{i-2}$，其特征方程为 $25a_i\cdot r^i+20a_i\cdot r^{i-1}=12\cdot r^{i-2}$，即 $25r^2+20r-12=0$。

解得 $r_1=\frac{2}{5},r_2=-\frac{6}{5}$。故通项公式形如 $a_n=A\cdot (\frac{2}{5})^n+B\cdot (-\frac{6}{5})^n$。由于 $a_0$ 已经确定，所以两系数和 $A+B=a_0$ 已经确定。

现在考虑解出 $A,B$，由于题目中要求 $a_i\geq 0$。我们来证明若 $B\neq0$，则一定存在 $a_i<0$。

为了方便，假定 $B>0$，$B<0$ 是类似的。当 $n$ 为奇数时， $(-\frac{6}{5})^n$ 为负数，所以 $A$ 必为正数。而当 $n>\log_3 \frac{A}{B}$ 时，有 $A\cdot (\frac{2}{5})^n<B (-\frac{6}{5})^n$，故存在 $a_i\geq0$。

所以 $B=0$，则 $A=a_0$，通项公式形如 $a_0\cdot (\frac{2}{5})^n$ 是等比数列。

区间覆盖等差数列，区间求和，可以用动态开点线段树完成。具体实现我相信做这道题的同学应该都比较熟悉，就不阐述了。

然后就……

（第一次被卡空成这样的我）

有两个比较好的空间优化：

• 询问时，如果到达的点是叶子结点，并且可以向下递归，可以直接用未下传的标记计算答案。
• 左节点和右节点可以只保存一个，生成节点时先生成左节点和右节点，来让编号连续。

Submission。