Codeforces Round #323 (Div. 2) D 582B Once Again...（快速幂）

A[i][j]表示在循环节下标i开头j结尾的最长不减子序列，这个序列的长度为p,另外一个长度为q的序列对应的矩阵为B[i][j]，

将两序列合并，新的序列对应矩阵C[i][j] = max(A[i][k]+B[k][j])。非法的情况标记为-INF，用倍增加速。

#include<bits/stdc++.h>
using namespace std;


const int INF = 0x3f3f3f3f;
const int maxn = 101;
int n;
typedef int MType;
struct Matrix
{
    MType dat[maxn][maxn];
    MType *operator [](int x){ return dat[x]; }
    Matrix operator | (Matrix& B) {
        Matrix re;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                re[i][j] = -INF;
                for(int k = 0; k < n; k++){
                    re[i][j] = max(re[i][j],dat[i][k]+B[k][j]);
                }
            }
        }
        return re;
    }
    Matrix operator ^ (int q){
        Matrix Re, A = *this;
        memset(Re.dat,0,sizeof(Re.dat));
        while(q){
            if(q&1){
                Re = Re | A;
            }
            A = A | A;
            q >>= 1;
        }
        return Re;
    }
};

int a[maxn];

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T; scanf("%d%d",&n,&T);
    for(int i = 0; i < n; i++){
        scanf("%d",a+i);
    }

    Matrix A;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(a[i]>a[j] ) A[i][j] = -INF;
            else {
                A[i][j] = 1;
                for(int k = 0; k < j; k++){
                    if(a[k] <= a[j])
                    A[i][j] = max(A[i][j],A[i][k]+1);
                }
            }
        }
    }
    A = A^T;
    int ans = 0;
    for(int i = 0; i < n;i++){
        for(int j = 0; j < n; j++){
            ans = max(ans,A[i][j]);
        }
    }
    printf("%d
",ans);
    return 0;
}