前缀和优化数列递推

$f_0 = 1$

$f_n = \sum_{i=0}^{n-1}f_i$

$n\le10^4$

考虑使用不完全归纳法。

$f_o=1,f_1=1,f_2=2,f_3=4,f_4=8 … $

唉,这东西好像就是二的幂次啊,是不是高精度莽一波就没了。

对于上面的递推式,一个做法是可以采用前缀和的优化方法:

即用 $sum_n = \sum_{i=0}^{n}f_i$ 来支持快速转移。

转移系数为多项式

考虑另一个问题:

Alice 有一个多项式

$$F(x) = \sum_{i=0}^{m}a_ix^i$$

Alice 还有一个递推式

$$f_0 = 1 $$

$$f_i = ((b_i \times (\sum_{j=0}^{i-1}f_j \times F(i-j))) \bmod P) ,\operatorname{xor},c_i$$

其中 $P = 10^9 + 7$

$A ,\operatorname{xor}, B$ 表示 $A$ 与 $B$ 的二进制不进位加法

其中 $n,m,{a_n},{b_n},{c_n}$ 是已知的。

Alice 想知道 $(\sum_{i=1}^{n}f[i]\times i^2) \bmod P$,请你帮助他求出这个值。

要求时间复杂度 $O(nm)$

考虑前缀和优化转移。

维护$\sum f_i \times F(x-i)$ 这样一个多项式

求值的时候只需要把 $x=i$ 代入就能得到之前的答案。

如何维护多项式?

一种常见的做法是维护数列的差分:

具体的,考虑一个已知多项式 $F(x)$。

维护 $F(x)$,我们可以维护 $F$ 的 $0 .. m$ 阶差分

例如,多项式$F(x)$ , 满足$F(0..5) = (0,1,4,9,16,25)$

$0,1,4,9,16,25$

$1,3,5,7,9,…$

$2,2,2,2,…$

记第 $i$ 行第 $j$ 个元素的值为 $a_{i,j}$

$a_{i,j} = a_{i,j-1} + a_{i-1,j+1}$

我们需要求的值相当于是$a_{0,n}$

容易通过前一列可以 $O(m)$ 求出下一列。

对于一个新增的 $f_n$ 的贡献,我们需要把 $f_n * F(x-n)$ 加入前缀和的统计中。

考虑两个多项式 $F,G$ ,$F+G$ 的差分数组的每一个位置就是 $F$的差分数组上的值 + $G$的差分数组上的值。

显然当我们确定一列的值之后,我们就能确定整个矩阵的所有值,而随着 $i$ 的递增,一个方便的做法是我们只维护第 $i$ 列的元素,没移动一个 $i$ 求出下一列。

容易发现 $F(x-n)$ 对于第 $n$ 列的贡献和 $F(x)$ 对于第 $0$ 列的贡献是一样的。

因此我们预处理求出贡献的系数,只需要 $O(m)$ 的时间复杂度就可以将 $f_n*F(x-n)$ 的贡献加入到差分数组中。

另一种做法是使用下降幂维护。

https://www.luogu.com.cn/paste/w35384yw

容易发现这两种做法本质相同。

以及另一种不是那么优秀的做法:

我发现如果对于所有 $i∈[0,n-1]$ 我将所有 $F(x-i)$ 都预处理好,问题是非常方便的。

考虑使用点值来存储一个多项式,那么我可以方便的进行多项式平移的操作。

对于一个通过点值存储的多项式,可以通过拉格朗日插值来快速求出某个点的值。

如果我们维护的是连续的点值,只需要求出 $F(-m)\sim F(n)$ ,即 $O(n+m)$ 个值,就可以快速得到整个多项式在平移 $0\sim n-1$ 个位置之后的值。

但是很遗憾,因为有拉格朗日插值,这个做法的常数较大。

但该做法扩展性较强,如规定只有一些位置才能快速转移,直接使用该做法的时间复杂度依然是 $O(nm)$ 的,而另外两个做法直接实现是 $O(nm^2)$的,可能还需要一些转化才能达到更有的复杂度(没想过)

比如解决下面一个问题

$F$ 是一个多项式

Alice 还有一个递推式

$$f_0 = 1 $$

$$f_i = \sum_{j=0}^{i-1}f_j \times F(i-j),col_i\ne col_j$$

其中 $n,m,{col_n}$ 是已知的。

Alice 想知道 $(\sum_{i=1}^{n}f[i]\times i^2) \bmod P$,请你帮助他求出这个值。

转移系数为递推式

当然,转移系数也可能不是多项式。

Alice 有一个递推式

给出 $F(0),F(1) .. F(m-1)$

以及递推关系 $F(n) = \sum_{i=1}^{m} a_i \times F(n-i)$

Alice 还有一个递推式

$$f_0 = 1 $$

$$f_i = ((b_i \times (\sum_{j=0}^{i-1}f_j \times F(i-j))) \bmod P) ,\operatorname{xor},c_i$$

其中 $P = 10^9 + 7$

$A ,\operatorname{xor}, B$ 表示 $A$ 与 $B$ 的二进制不进位加法

其中 $n,m,{a_n},{b_n},{c_n}$ 是已知的。

Alice 想知道 $(\sum_{i=1}^{n}f[i]\times i^2) \bmod P$,请你帮助他求出这个值。

首先我们可以很容易想到一个基于常系数齐次线性递推的做法。

即根据 凯莱-哈密顿定理零化多项式 ,发现每个 $F(n)$ 都可以写成 $F(0) \sim F(m-1)$ 的线性组合。

具体的,维护 $\sum_{j=0}^{n} f_j*\times F(n-j) x^{n-j}$ 对零化多项式取膜后的结果,发现往后转移转移一个位置相当于整个多项式乘上一个 $x$ , 再进行取膜。由于移动一位只会有一项多余,因此直接实现的时间复杂度依然是 $O(m)$ 的。

至于递推式的零化多项式……应该已经烂大街了。

其实也可以直接理解成直接递推……

当然,我们还有另外一个做法。

在阐述这个做法之前,我们假设一个前提:我们知道递推式的通项公式,即 $F(n) = \sum_{i=1}^{m} a_i \times b_i^n$

根据前缀和优化数列递推的思路,我们对于每一个 $i$ ,都维护 $a_i\sum_{j=0}^{n} f_j \times b_i^{n-j}$ , 发现移动一位只需要乘上一个 $b_i$ 即可,非常方便。

值得注意的是,这个做法可以进行一个小小的扩展。

比如解决下面一个问题

$F$ 是一个递推式

Alice 还有一个递推式

$$f_0 = 1 $$

$$f_i = \sum_{j=0}^{i-1}f_j \times F(i-j),col_i\ne col_j$$

其中 $n,m,{col_n}$ 是已知的。

Alice 想知道 $(\sum_{i=1}^{n}f[i]\times i^2) \bmod P$,请你帮助他求出这个值。

关于求递推式通项公式,可以参考 具体数学 7.3 解递归式

如果保证特征多项式没有重根或许会好做很多。

当递推式是固定的情况下,可以手动解通项公式。

感谢 zzd233 与我交流讨论相关问题与解法

文章目录
  1. 1. 转移系数为多项式
  2. 2. 转移系数为递推式
|