清空网站空间,邯郸信息港二手车出售,seo体系,网站的规划和建设方案线性递推数列
线性递推
对于无限数列 {a0,a1,...}\{a_0,a_1,...\}{a0,a1,...} 和有限非空数列 {r0,r1,...,rm−1}\{r_{0},r_1,...,r_{m-1}\}{r0,r1,...,rm−1} 。
若对于任意 m−1≤nm-1\le nm−1≤n #xff0c;有 ∑i0m−1an−iri0\sum_{i0}^{m-1}a_{n-i}r_i0∑…线性递推数列
线性递推
对于无限数列 {a0,a1,...}\{a_0,a_1,...\}{a0,a1,...} 和有限非空数列 {r0,r1,...,rm−1}\{r_{0},r_1,...,r_{m-1}\}{r0,r1,...,rm−1} 。
若对于任意 m−1≤nm-1\le nm−1≤n 有 ∑i0m−1an−iri0\sum_{i0}^{m-1}a_{n-i}r_i0∑i0m−1an−iri0 则称数列 rrr 为数列 aaa 的线性递归式。
若 r01r_01r01称数列 rrr 为数列 aaa 的线性递推式。
称存在线性递推式的无限数列为线性递推数列。
r01r_01r01 说明可以写成 an−(an−1∗r1an−2∗r2...an−m1∗rm−1)a_n-(a_{n-1}*r_1a_{n-2}*r_2...a_{n-m1}*r_{m-1})an−(an−1∗r1an−2∗r2...an−m1∗rm−1)。
对于有限数列 {a0,a1,...an−1}\{a_0,a_1,...a_{n-1}\}{a0,a1,...an−1} 和有限非空数列 {r0,r1,...,rm−1}\{r_{0},r_1,...,r_{m-1}\}{r0,r1,...,rm−1} 。
若对于任意 m−1≤p≤nm-1\le p\le nm−1≤p≤n 有 ∑i0m−1ap−iri0\sum_{i0}^{m-1}a_{p-i}r_i0∑i0m−1ap−iri0 则称数列 rrr 为数列 aaa 的线性递归式。
若 r01r_01r01称数列 rrr 为数列 aaa 的线性递推式。
称这个线性递推式的阶数为它的长度 −1-1−1。因为下标是从 000 开始的
称数列 aaa 阶数最小的线性递推式为数列 aaa 的最短线性递推式。
生成函数
对于有限数列 {a0,...,an−1}\{a_0,...,a_{n-1}\}{a0,...,an−1}定义它的生成函数为多项式 A(x)∑i0n−1aixiA(x)\sum_{i0}^{n-1}a_ix^iA(x)∑i0n−1aixi。
对于无限数列 {a0,a1,...}\{a_0,a_1,...\}{a0,a1,...}定义它的生成函数为形式幂级数 A(x)∑0∞aixiA(x)\sum_{0}^∞a_ix^iA(x)∑0∞aixi。
对于无限数列 {a0,a1,...}\{a_0,a_1,...\}{a0,a1,...} 和有限非空数列 {r0,r1,...,rm−1}\{r_{0},r_1,...,r_{m-1}\}{r0,r1,...,rm−1} 。
设数列 aaa 的生成函数为 AAA数列 rrr 的生成函数为 RRR。
数列 rrr 为数列 aaa 的线性递归式等价于存在次数不超过 m−2m-2m−2 次的多项式 CCC满足 ARC0ARC0ARC0。
对于有限数列 {a0,a1,...,an−1}\{a_0,a_1,...,a_{n-1}\}{a0,a1,...,an−1} 和有限非空数列 {r0,r1,...,rm−1}\{r_{0},r_1,...,r_{m-1}\}{r0,r1,...,rm−1} 。
设数列 aaa 的生成函数为 AAA数列 rrr 的生成函数为 RRR。
数列 rrr 为数列 aaa 的线性递归式等价于存在次数不超过 m−2m-2m−2 次的多项式 CCC满足 ARC≡0(modxn)ARC\equiv 0\pmod {x^n}ARC≡0(modxn)。
Berlekamp-Massey
注意上面的都是下标从 000 开始这里的算法流程下标是从 111 开始的。
Berlekamp-Massey 算法是用来在 O(n2)O(n^2)O(n2) 的时间里求一个数列的最短线性递推式。
方法思想是增量法。 重申明确一下问题模型给定 nnn 个元素的数列 a1,...ana_1,...a_na1,...an求一个最短的数列 r1,...rmr_1,...r_mr1,...rm。要求满足 ∀mi≤nai∑j1mai−jrj\forall_{mi\le n}\ a_i\sum_{j1}^{m}a_{i-j}r_j∀mi≤n ai∑j1mai−jrj。要求在 O(n2)O(n^2)O(n2) 时间内解决。 注意1这个递推的下标可以看作是一种卷积形式相加和为一个“定值”这有利于你快速理解下面的一些下标变换与对应。 注意2这个条件只需要 mmm 的下标做到换言之如果被当成了 rrr 中的一个“基”是不需要满足这个式子的因为会有下标为负的情况。 注意3aia[i]a(i)a_ia[i]a(i)aia[i]a(i) 只是表达方式不同。
假设递推式已经经过了 ttt 次更新第 iii 次更新的递推式记为 r(i)r(i)r(i)这是一个多项式长度为 m(i)m(i)m(i)。初始时定义 r(0)∅,m(0)0r(0)\empty,m(0)0r(0)∅,m(0)0。
一个一个考虑加入数列 aaa 中元素现在即将加入 aia_iai。假设现在递推式长度为 mm(t)mm(t)mm(t)。
设 Δ(i)ai−∑j1ma[i−j]⋅r(i)[j]\Delta(i)a_i-\sum_{j1}^ma[i-j]·r(i)[j]Δ(i)ai−∑j1ma[i−j]⋅r(i)[j]。 Δ(i)0\Delta(i)0Δ(i)0证明目前递推式仍然满足条件合法不用修改继续考虑加入下一个。 Δ(i)≠0\Delta(i)\neq 0Δ(i)0。设 fail(t)i\text{fail}(t)ifail(t)i表示 r(t)r(t)r(t) 递推式第一次失效的位置在 iii。 t0t0t0。 意味着 aia_iai 前面的数都为 000。那么不管递推数列怎么配求和都是 000。显然只能将 iii 这个下标也被递推式包含。 所以新的递推式直接就是 r(t1){0,0,...,0⏟i}r(t1)\{\underbrace{0,0,...,0}_i\}r(t1){i0,0,...,0}。 这样就不需要 aia_iai 满足上面求和的式子了它已经作为递推式的一个“基”了。 t≠0t\ne 0t0。 考虑构造一个递推式 RRR满足 ∀∣R∣ki∑j1∣R∣ak−jRj0\forall_{|R|ki}\ \sum_{j1}^{|R|}a_{k-j}R_j0∀∣R∣ki ∑j1∣R∣ak−jRj0∑j1∣R∣ai−jRjΔ(i)\sum_{j1}^{|R|}a_{i-j}R_j\Delta(i)∑j1∣R∣ai−jRjΔ(i)。 寻找之前某次失效的递推式0≤pt0\le pt0≤pt显然这个递推式的失效位置为 fail(p)\text{fail}(p)fail(p)。 同时设 ωΔ(i)Δ(fail(p))\omega\frac{\Delta(i)}{\Delta\big(\text{fail}(p)\big)}ωΔ(fail(p))Δ(i)则 R{0,0,…,0⏟i−fail(p)−1,ω,−ω⋅r(p)[1],−ω⋅r(p)[2],...,−ω⋅r(p)[∣r(p)∣]}R\{\underbrace{0,0,…,0}_{i-\text{fail}(p)-1},\omega,-\omega·r(p)[1],-\omega·r(p)[2],...,-\omega·r(p)\Big[\big|r(p)\big|\Big]\}R{i−fail(p)−10,0,…,0,ω,−ω⋅r(p)[1],−ω⋅r(p)[2],...,−ω⋅r(p)[∣∣r(p)∣∣]}。 令 r(t1)r(t)Rr(t1)r(t)Rr(t1)r(t)R 即可。加法遵循多项式加法原则即对位系数相加 中场休息——请确保上面的下标之间关系理清楚了再继续往下看正确性 为什么这样是对的理论解释不清楚不妨眼见为实我们直接带进去算。 对于 aia_iai。 R[1,i−fail(p)−1]R[1,i-\text{fail}(p)-1]R[1,i−fail(p)−1] 都为 000对应 a[i−1,fail(p)1]a[i-1,\text{fail}(p)1]a[i−1,fail(p)1] 相乘和为 000。 真正乘起来有值的是从 R[i−fail(p)]↔a[fail(p)]R\big[i-\text{fail}(p)\big]\leftrightarrow a\big[\text{fail}(p)\big]R[i−fail(p)]↔a[fail(p)] 项开始的。 并且后面对应相乘r(p)[1]↔a[fail(p)−1],r(p)[2]↔a[fail(p)-2]......r(p)[1]\leftrightarrow a[\text{fail}(p)-1],r(p)[2]\leftrightarrow a[\text{fail(p)-2}]......r(p)[1]↔a[fail(p)−1],r(p)[2]↔a[fail(p)-2]...... 等等 这相乘求和不就是第 ppp 个递推式失效的位置对应的表达式吗转化一下即 afail(p)−Δ(fail(p))a_{\text{fail(p)}}-\Delta\big(fail(p)\big)afail(p)−Δ(fail(p))。 ⇒ω⋅afail(p)−ω⋅(afail(p)−Δ(fail(p)))ω∗Δ(fail(p))Δ(i)\Rightarrow \omega·a_{\text{fail(p)}}-\omega·\Big(a_{\text{fail(p)}}-\Delta\big(\text{fail}(p)\big)\Big)\omega*\Delta\big(\text{fail}(p)\big)\Delta(i)⇒ω⋅afail(p)−ω⋅(afail(p)−Δ(fail(p)))ω∗Δ(fail(p))Δ(i)。 发现 RRR 把 r(t)r(t)r(t) 失效的差距部分恰好补上了。 由此可知 r(t1)r(t1)r(t1) 对 aia_iai 成立。 对于 m≤kim\le kim≤ki。其实推导与上面差不多。 R[1,i−fail(p)−1]R[1,i-\text{fail}(p)-1]R[1,i−fail(p)−1] 都为 000对应 a[k−1,k−ifail(p)1]a[k-1,k-i\text{fail}(p)1]a[k−1,k−ifail(p)1] 相乘和为 000。 真正乘起来有值的是从 R[i−fail(p)]↔a[k−ifail(p)]R\big[i-\text{fail}(p)\big]\leftrightarrow a\big[k-i\text{fail}(p)\big]R[i−fail(p)]↔a[k−ifail(p)] 项开始的。 并且后面对应相乘r(p)[1]↔a[k−ifail(p)−1],r(p)[2]↔a[k−ifail(p)-2]......r(p)[1]\leftrightarrow a[k-i\text{fail}(p)-1],r(p)[2]\leftrightarrow a[k-i\text{fail(p)-2}]......r(p)[1]↔a[k−ifail(p)−1],r(p)[2]↔a[k−ifail(p)-2]...... 转化一下即 ak−ifail(p)−Δ(k−ifail(p))a_{k-i\text{fail}(p)}-\Delta(k-i\text{fail}(p))ak−ifail(p)−Δ(k−ifail(p))。 因为 kikiki所以 k−ifail(p)fail(p)k-i\text{fail}(p)\text{fail}(p)k−ifail(p)fail(p)。 还记得 fail(p)\text{fail}(p)fail(p) 的定义吗——是 r(p)r(p)r(p) 第一个失效的位置。换言之在此位置之前 r(p)r(p)r(p) 都是成立的。 所以 Δ(k−ifail(p))0\Delta(k-i\text{fail}(p))0Δ(k−ifail(p))0。 ⇒ω⋅ak−ifail(p)−ω⋅(ak−ifail(p)−Δ(k−ifail(p)))ω∗Δ(k−ifail(p))0\Rightarrow \omega·a_{k-i\text{fail(p)}}-\omega·\Big(a_{k-i\text{fail(p)}}-\Delta\big(k-i\text{fail}(p)\big)\Big)\omega*\Delta\big(k-i\text{fail}(p)\big)0⇒ω⋅ak−ifail(p)−ω⋅(ak−ifail(p)−Δ(k−ifail(p)))ω∗Δ(k−ifail(p))0。 综上我们构造的这个 RRR 本质上只起到了对 aia_iai 补充 Δ(i)\Delta(i)Δ(i) 的效果对于其余 kkk 的贡献都是 000。 这是利用了 r(p)r(p)r(p) 在 1∼fail(p)−11\sim \text{fail}(p)-11∼fail(p)−1 都满足关系而在 fail(p)\text{fail}(p)fail(p) 相差 Δ(p)\Delta(p)Δ(p) 的性质。 此外我们还希望递推式的长度越短越好也就是说 max(m(t),i−fail(p)m(p))\max\big(m(t),i-\text{fail}(p)m(p)\big)max(m(t),i−fail(p)m(p)) 最短。 贪心地只需要动态维护最短的 i−fail(p)m(p)i-\text{fail}(p)m(p)i−fail(p)m(p)每次算出 r(t1)r(t1)r(t1) 时都与之前的 r(p)r(p)r(p) 比一下谁更短即可。
一共递推 O(n)O(n)O(n) 次每次修改 O(n)O(n)O(n) 次时间复杂度为 O(n2)O(n^2)O(n2)。
代码实现中rrr 用的是 vector\text{vector}vector下标从 000 开始所以有些下标会与上面的推导略有差异。且不保证一定正确
//std参考code
#include bits/stdc.h
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 1005
int n, cnt;
int a[maxn], fail[maxn], delta[maxn];
vector int r[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 1;i n;i )if( ! cnt ) {if( a[i] ) {fail[cnt ] i;delta[i] a[i];r[cnt].resize( i, 0 );}continue;}else {fail[cnt] i;delta[i] a[i];for( int j 0;j r[cnt].size();j ) ( delta[i] - a[i - j - 1] * r[cnt][j] ) % mod;if( ! delta[i] ) continue;// int len 0x7f7f7f7f, p;int len i - fail[cnt - 1] r[cnt - 1].size(), p cnt - 1;for( int j 0;j cnt;j )if( i - fail[j] r[j].size() len )len i - fail[j] r[j].size(), p j;int omega delta[i] * qkpow( delta[fail[p]], mod - 2 ) % mod;r[cnt 1] r[cnt];cnt ;while( r[cnt].size() len ) r[cnt].push_back( 0 );( r[cnt][i - fail[p] - 1] omega ) % mod;for( int j 0;j r[p].size();j )( r[cnt][i - fail[p] j] - omega * r[p][j] ) % mod; }printf( %lld\n, r[cnt].size() );for( int i : r[cnt] ) printf( %lld , ( i mod ) % mod );return 0;
}
/*
Input 1
7
1 2 4 9 20 40 90
Output 1
4
0 0 10 0Input 2
18
2 4 8 16 32 64 128 256 512 2 4 8 16 32 64 128 256 512
Output 2
0 0 0 0 0 0 0 0 1
*/BM算法和线性递推的应用
当我们确信这个题是 矩阵加速 / 线性递推 的题且矩阵很难构造。
那么可以 暴力递推/打表 出超过两倍矩阵阶数的长度然后 BM线性递推 得到这个序列的任意项。
不知道矩阵阶数就 能找多长,找多长 了。
某些特殊情况下也可以代替 DFA的最小化 。
打表题也可以试着找一下规律因为只能找线性递推的规律所以大部分情况要灵活处理比如说先差分再找规律之类的。
