一种用来求最短线性递推的奇妙算法。复杂度是 $O(n^2)$ 。

忘了怎么做建议看看这个博客，很清楚了。

模板题 CF848E

int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}

int del[MAXN];
vi BM( vi a ) { 
	vi re , las;
	int fail = -1 , n = a.size();
	for( int i = 0 ; i < n ; ++ i ) {
		del[i] = a[i];
		for( int j = 0 ; j < re.size() ; ++ j ) del[i] = ( del[i] + P - a[i - j - 1] * 1ll * re[j] % P ) % P;
		if( !del[i] ) continue;
		if( fail == -1 ) { fail = i , re.resize( i + 1 ); continue; }
		int mu = del[i] * 1ll * Pow( del[fail] , P - 2 ) % P;
		vi tmp = re; re.clear() , re.resize( i - fail - 1 ) , re.pb( mu );
		for( int x : las ) re.pb( x * 1ll * ( P - mu ) % P );
		fail = i , las = tmp;
		if( re.size() < las.size() ) re.resize( tmp.size() );
		for( int i = 0 ; i < tmp.size() ; ++ i ) re[i] = ( re[i] + tmp[i] ) % P;
	}
	return re;
}