Codeforces Round #230 (Div. 1) C题 （复合矩阵连乘）

    Codeforces Round #230 (Div. 1) C题  （复合矩阵连乘）

    这题关键是要想到把系数矩阵复合到原来的斐波那契矩阵当中，然后矩阵连乘。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#define ll __int64
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;

int k , K ; ll n ;

struct ret {
    ll dir[88][88] ;
} e , E ;

ll c[44][44] ;
const ll mod = 1000000007 ;

void muil ( ret x , ret y , ret &z ) {
    int i , j , l ;
    for ( i = 0 ; i < K ; i ++ )
        for ( j = 0 ; j < K ; j ++ )
            for ( l = 0 ; l < K ; l ++ ) {
                if ( l == 0 ) z.dir[i][j] = x.dir[i][l] * y.dir[l][j] ;
                else z.dir[i][j] += x.dir[i][l] * y.dir[l][j] ;
                z.dir[i][j] %= mod ;
            }
}

void init ( int n ) {
    memset ( e.dir , 0 , sizeof ( e.dir ) ) ;
    int i , j ;
    for ( i = 0 ; i <= 40 ; i ++ ) {
        c[i][0] = 1 ;
        for ( j = 1 ; j <= i ; j ++ )
            c[i][j] = ( c[i-1][j] + c[i-1][j-1] ) % mod ;
    }
    for ( i = 0 ; i <= n ; i ++ )
        for ( j = 0 ; j <= i ; j ++ )
            e.dir[i+n+1][j] = e.dir[i][j+n+1] = e.dir[i][j] = c[i][j] ;
    for ( i = 0 ; i < K ; i ++ ) E.dir[i][i] = 1 ;
    e.dir[2*(n+1)][n] = e.dir[2*(n+1)][2*(n+1)] = 1 ;
}

ll gao ( ll n ) {
    ret ans = E , f = e ;
    while ( n ) {
        if ( n & 1 ) muil ( ans , f , ans ) ;
        muil ( f , f , f ) ;
        n >>= 1 ;
    }
    ll fuck = 0 ;
    for ( int i = 0 ; i < K - 1 ; i ++ )
        fuck = ( fuck + ans.dir[K-1][i] ) % mod ;
    return fuck ;
}

int main() {
    scanf ( "%I64d%d" , &n , &k ) ;
    if ( n == 1 ) {
        puts ( "1" ) ;
        return 0 ;
    }
    K = (k+1) * 2 + 1 ;
    init ( k ) ;
    printf ( "%I64d\n" , gao ( n ) ) ;
    return 0;
}

Codeforces Round #230 (Div. 1) C题 （复合矩阵连乘）

原文：http://blog.csdn.net/no__stop/article/details/19486353