[Easy-Medium] P11735 [集训队互测 2015] 胡策的数列
xiezheyuan
·
·
题解
简要题意
有一个数列 a_i 满足：
- 对于 i\geq2 有 25a_i+20a_{i-1}=12a_{i-2}。
-
给定一个长度为 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 取模。
## 思路
先来解递推式。
对于 $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](https://uoj.ac/submission/737822)。