BZOJ-3231: [Sdoi2008]递归数列（矩阵快速幂）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3231

矩阵快速幂搞一搞。。。记得把Sn也维护进矩阵里。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define ll long long
#define MAXN 20
#define rep( i , x ) for ( ll i = 0 ; i < x ; ++ i )
 
ll mod ;
 
struct mat {
     
    ll n , m , a[ MAXN ][ MAXN ] ;
     
    mat(  ) {
        n = m = 0 ;
        memset( a , 0 , sizeof( a ) ) ;
    }
     
    void I( int _n ) {
        n = m = _n ;
        rep( i , n ) a[ i ][ i ] = 1 ;
    }
     
};
 
mat operator * ( const mat &x , const mat &y ) {
    mat ret ;
    ret.n = x.n , ret.m = y.m ;
    rep( i , ret.n ) rep( j , ret.m ) rep( k , x.m ) {
        ( ret.a[ i ][ j ] += x.a[ i ][ k ] * y.a[ k ][ j ] ) %= mod ;
    }
    return ret ;
}
 
mat power( mat x , ll cnt ) {
    mat ret ; ret.I( x.n ) ;
    for ( ; cnt ; cnt >>= 1 ) {
        if ( cnt & 1 ) ret = ret * x ;
        x = x * x ;
    }
    return ret ;
}
 
ll n , m , k , b[ MAXN ] , c[ MAXN ] , sum[ MAXN ] ;
mat ori , e ;
 
ll SUM( ll cnt ) {
    if ( cnt <= k ) return sum[ cnt ] ;
    mat ret = power( e , cnt - k ) * ori ;
    ll rec = ( ret.a[ 0 ][ 0 ] + ret.a[ 1 ][ 0 ] ) % mod ;
    return rec ;
}
 
int main(  ) {
    memset( sum , 0 , sizeof( sum ) ) ;
    scanf( "%lld" , &k ) ;
    for ( int i = 0 ; i ++ < k ; ) scanf( "%lld" , b + i ) ;
    for ( int i = 0 ; i ++ < k ; ) scanf( "%lld" , c + i ) ;
    scanf( "%lld%lld%lld" , &m , &n , &mod ) ;
    e.n = e.m = k + 1 ;
    e.a[ 0 ][ 0 ] = e.a[ 0 ][ 1 ] = 1 ;
    for ( int i = 0 ; i ++ < k ; ) e.a[ 1 ][ i ] = c[ i ] % mod ;
    for ( int i = 1 ; i ++ < k ; ) e.a[ i ][ i - 1 ] = 1 ;
    for ( int i = 0 ; i ++ < k ; ) ( sum[ i ] = sum[ i - 1 ] + b[ i ] ) % mod ;
    ori.n = k + 1 , ori.m = 1 ;
    ori.a[ 0 ][ 0 ] = sum[ k - 1 ] ;
    for ( int i = 0 ; i ++ < k ; ) ori.a[ i ][ 0 ] = b[ k - i + 1 ] ;
    ll x = SUM( n ) , y = SUM( m - 1 ) ;
    ll ans = x - y ;
    while ( ans < 0 ) ans += mod ;
    printf( "%lld\n" , ans ) ;
    return 0 ; 
}