マトリックスクラスバックアップ

1741 ワード 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 
# include 

# define ll long long

using namespace std ;

const ll mod = 1e9 + 7 ;
const int maxlen = 101 ;
int cnt ;

struct MATR {
    ll a [ maxlen + 1 ] [ maxlen + 1 ] ;

    void initunit ( ) {
        for ( int i = 1 ; i <= cnt ; i ++ ) {
            for ( int j = 1 ; j <= cnt ; j ++ ) {
                a [ i ] [ j ] = ( i == j ? 1 : 0 ) ;
            }
        }
    }

    void initzero ( ) {
        memset ( a , 0 , sizeof ( a ) ) ;
    }

    void modul ( ) {
        for ( int i = 0 ; i < cnt ; i ++ ) {
            for ( int j = 0 ; j < cnt ; j ++ ) {
                a [ i ] [ j ] %= mod ;
            }
        }
    }

    friend MATR operator * ( MATR a , MATR b ) {
        MATR ans ;
        ans . initzero ( ) ;
        for ( int i = 1 ; i <= cnt ; i ++ )
            for ( int j = 1 ; j <= cnt ; j ++ )
                if ( a . a [ i ] [ j ] )
                    for ( int k = 1 ; k <= cnt ; k ++ )
                        ans . a [ i ] [ k ] += a . a [ i ] [ j ] * b . a [ j ] [ k ] ;
        ans . modul ( ) ;
        return ans;
    }

    friend MATR operator ^ ( MATR a , int n ) {
        MATR ans ;
        ans . initunit ( ) ;
        while ( n ) {
            if ( n & 1 ) {
                ans = ans * a ;
            }
            a = a * a ;
            n >>= 1 ;
        }
        return ans ;
    }
} ;
[伯俊]BOJ 14719雨水JAVA
[プログラマ](python)小数点を検索