Luogu P1939 矩阵加速

矩阵快速幂的模板题，推到过程很简单
\[\begin{matrix}a[i] = 1\times a[i-1] + 0\times a[i-2]+1\times a[i-3]\\a[i-1] = 1\times a[i-1] + 0\times a[i-2]+0\times a[i-3]\\a[i-2] = 0\times a[i-1] + 1\times a[i-2]+0\times a[i-3]\\\Downarrow \\\begin{bmatrix}f[i]\\f[i-1]\\f[i-2]\end{bmatrix}=\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}\times \begin{bmatrix}f[i-1]\\f[i-2]\\f[i-3]\end{bmatrix}\end{matrix}\]
直接暴力矩阵快速幂是可以过的，但有没有优化呢？

我们考虑离线来做这道题

首先我们把所有的数据读入，然后离散化，并排序

对与\(ans_i\)我们可以计算\(d=n_i-n_i\)得到一个差值

然后只需将\(ans_{i-1}\)乘上状态转移矩阵\(f\)的\(d\)次方，就是\(ans_i\)

可以通过这种操作来减少多次重复的运算

#include <bits/stdc++.h>
#define LL long long
using namespace std;


const int N = 105 , M = 5 , mod = 1e9 + 7;
int n , key[N] , val[N] , ans[N];

struct matrix
{
    int x , y;
    LL v[M][M];

    matrix() { memset( v , 0 , sizeof(v) ); }

    inline friend matrix operator *  (matrix a , matrix b )
    {
        register matrix cur;
        cur.x = a.x , cur.y = b.y;
        for( register int i = 1 ; i <= cur.x ; i ++ )
        {
            for( register int j = 1 ; j <= cur.y ; j ++ )
            {
                cur.v[i][j] = 0;
                for( register int k = 1 ; k <= a.y ; k ++ ) cur.v[i][j] = ( cur.v[i][j] + a.v[i][k] % mod * b.v[k][j] % mod ) % mod;
            }
        }
        return cur;
    }
} f , res;


inline LL read()
{
    register LL x = 0;
    register char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' )
    {
        x = ( x << 3 ) + ( x << 1 ) + ch - '0';
        ch = getchar();
    }
    return x;
}

inline void matrix_I( matrix &t , int k)//构造单位矩阵
{
    t.x = t.y = k;
    for( register int i = 1 ; i <= k ; i ++ ) t.v[i][i] = 1;
}

inline matrix matrix_power( matrix x , int k )//矩阵快速幂
{
    if( k == 1 ) return x;
    register matrix t; matrix_I( t , 3 );
    while( k )
    {
        if( k & 1 ) t = t * x ;
        x = x * x;
        k >>= 1;
    }
    return t;
}

inline void init()
{
    f.x = f.y = 3;
    memset( f.v , 0 , sizeof( f.v ) );
    f.v[1][1] = f.v[1][3] = f.v[2][1] = f.v[3][2] = 1 ;
}


int main()
{
    n = read();
    for( register int i = 1 ; i <= n ; i ++ ) key[i] = val[i] = read();
    sort( val + 1 , val + 1 + n ) ;
    for( register int i = 1 ; i <= n ; i ++ ) key[i] = lower_bound( val + 1 , val + 1 + n , key[i] ) - val;
    res.x = 3 , res.y = res.v[1][1] = res.v[2][1] = res.v[3][1] = 1;
    val[0] = 3;
    for( register int i = 1 ; i <= n ; i ++ )
    {
        if( val[i] <= 3 ) { ans[i] = 1 , val[i] = 3 ; continue; }
        register int d = val[i] - val[ i - 1 ];//计算差值
        if( d == 0 ) //特殊情况
        {
            ans[i] = ans[ i - 1 ] ;
            continue;
        }
        init();//初始化 矩阵f
        f = matrix_power( f , d );
        res = f * res;
        ans[i] = res.v[1][1] % mod;
    }
    for( register int i = 1 ; i <= n ; i ++ ) printf( "%d\n" , ans[ key[i] ] );
    return 0;
}