LHPC 2016 pD. 九連環 ( Hanoi's Tower + Fast Matrix Multiplication )

蠻有趣的一道題。首先要觀察當 N ≥ 3 的時候，其實是先進行一次 N - 2 的子問題，取走最下面的盤子，然後再反著做一次 N - 2 的子問題，經過這三個步驟之後轉換成 N - 1 的子問題，遞迴下去，直到 N ≤ 2 直接解決。因此令 f( N ) 為 N 個環的步驟數，會有

但 N 最大可能到 1e17，因此考慮用轉移矩陣解決，確切的轉移為

const int m = 1e9 + 7;
typedef vvi mat;
typedef vi vec;

mat mul(const mat &e, const mat &f){
    assert( e[ 0 ].size() == f.size() );
    mat h( e.size(), vec( f[ 0 ].size() ) );
    for(int i = 0; i < e.size(); ++i)
        for(int j = 0; j < f[ 0 ].size(); ++j)
            for(int k = 0; k < f.size(); ++k)
                ( h[ i ][ j ] += 1LL * e[ i ][ k ] * f[ k ][ j ] % m ) %= m;
    return h;
}

mat fastpow(mat e, ll p){
    mat f( e.size(), vec( e[ 0 ].size() ) );
    for(int i = 0; i < e.size(); ++i)
        f[ i ][ i ] = 1;
    while( p > 0 ){
        if( p & 1LL ) f = mul( f, e );
        p >>= 1LL;
        e = mul( e, e );
    }
    return f;
}

vi print( int n ){
    vi res;
    if( n == 1 ){
        res.push_back( 1 );
        return res;
    }
    if( n == 2 ){
        res.push_back( 2 );
        res.push_back( 1 );
        return res;
    }
    vi z = print( n - 2 );
    for( int i = 0; i < z.size(); ++i ) res.push_back( z[ i ] );
    res.push_back( n );
    for( int i = z.size() - 1; i >= 0; --i ) res.push_back( z[ i ] );
    z = print( n - 1 );
    for( int i = 0; i < z.size(); ++i ) res.push_back( z[ i ] );
    return res;
}

void solve(){
    ll N; cin >> N;
    if( N <= 10 ){
        vi ans = print( N );
        cout << ans.size() << endl;
        vi out( N + 1 );
        for( int i = 0; i < ans.size(); ++i ){
            cout << "Move ring " << ans[ i ] << " ";
            out[ ans[ i ] ] ^= 1;
            if( out[ ans[ i ] ] ) cout << "out\n";
            else cout << "in\n";
        }
        return;
    }
    N -= 2;
    mat t( 3, vec( 3 ) );
    t = { { 1, 2, 1 }, { 1, 0, 0 }, { 0, 0, 1 } };
    mat x( 3, vec( 1 ) );
    x = { { 2 }, { 1 }, { 1 } };
    x = mul( fastpow( t, N ), x );
    cout << x[ 0 ][ 0 ] << endl;
}