CFR 583 D. Once Again... ( DP + Fast Matrix MAXiplication )

Problem - D - Codeforces
I thought this was quite difficult, despite the technique required was not that advanced.
The key is to come up with the dp form:
dp[ i ][ j ][ k ] : maximal length of non-decreasing subsequence of A concatenated k times, such that the first value is greater or equal to A[ i ], and the ending value is A[ j ]
... ( See, it's not that instinctive to imagine of, at least in my view )
With this form, we can easily perform concatenation, which gives us recursive function for dp:
dp[ i ][ j ][ k ] = max{ dp[ i ][ m ][ k - 1 ] + dp[ m ][ j ][ k -1 ] }, for all A[ i ] ≤ A[ m ] ≤ A[ j ]
And since commutative and associative law both apply on MAX, we can put it in form of matrix multiplication to attain optimization, where the identity matrix will be O instead of 1s in the diagonal.
So we will first compute dp[ i ][ j ][ 0 ] for all ( i, j ) with brute force, O( N ^ 3 ). Then, use matrix multiplication, O( N ^ 3 lg T ).
Here's another one pertaining to XOR and AND with similar technique on fast matrix multiplication.

vector< vector< bool > > has_path; // has_path[ i ][ j ] == 1 <=> A[ i ] ≤ A[ j ]

vvi mat_mul( const vvi &a, const vvi &b ){
    vvi res( a.size(), vi( b[ 0 ].size() ) );
    for( int i = 0; i < a.size(); ++i )
        for( int k = 0; k < a[ 0 ].size(); ++k )
            for( int j = 0; j < b[ 0 ].size(); ++j )
                if( has_path[ i ][ k ] and has_path[ k ][ j ] )
                    upmax( res[ i ][ j ], a[ i ][ k ] + b[ k ][ j ] );
    return res;
}

vvi mat_pow( vvi x, int p ){
    vvi res( x.size(), vi( x[ 0 ].size() ) );
    while( p ){
        if( p & 1 )
            res = mat_mul( res, x );
        p >>= 1;
        x = mat_mul( x, x );
    }
    return res;
}

void solve(){
    int N, T; cin >> N >> T;
    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];

    has_path = vector< vector< bool > >( N, vector< bool >( N ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j )
            if( A[ i ] <= A[ j ] )
                has_path[ i ][ j ] = true;

    vvi dp( N, vi( N, 0 ) );
    for( int i = 0; i < N; ++i )
        if( has_path[ i ][ 0 ] )
            dp[ i ][ 0 ] = 1;

    for( int j = 1; j < N; ++j ){
        for( int k = 0; k < N; ++k )
            if( has_path[ k ][ j ] )
                dp[ k ][ j ] = 1;
        for( int k = 0; k < j; ++k )
            if( has_path[ k ][ j ] )
                for( int m = 0; m < N; ++m )
                    if( has_path[ m ][ k ] )
                        upmax( dp[ m ][ j ], dp[ m ][ k ] + 1 );
    }

    dp = mat_pow( dp, T );

    int ans = 0;
    for( int i = 0; i < dp.size(); ++i )
        for( int j = 0; j < dp[ i ].size(); ++j )
            upmax( ans, dp[ i ][ j ] );

    cout << ans << endl;
}