Codeforces Round #420 (Div. 2) E. Okabe and El Psy Kongroo dp+矩阵快速幂

E. Okabe and El Psy Kongroo dp+矩阵快速幂

My Solution

题意：从(0,0)走到(k,0)(1 ≤ k ≤ 1e18)，每次可以从(x, y) 走到 (x+1, y+1) 或 (x+1, y) 或 (x+1, y-1)，然后必须在很多个y == ci的线段下面走，

(相邻的线段，前一个的结束x坐标bi和后一个线段的开始x坐标ai+1 相同，且y = ci可能不同)

dp+矩阵快速幂

比较裸的dp+矩阵快速幂，因为这里k为1e18，所以几乎只能用矩阵快速幂来做了。

朴素的dp，dpij表示走到(i, j)时的方案数，

则 状态方程为，if(j+1 <= b[k]) dp[i+1][j+1] += dp[i][j];

if(j-1 >= 0) dp[i+1][j-1] += dp[i][j];

dp[i+1][j] += dp[i][j];

然后可以构造出15*15(ci<=15)的矩阵，把状态转移到矩阵上，然后对于每个a[k]、b[k]、c[k]跑一次快速幂即可。

此外注意a[k]，b[k]，以及快速幂的参数到是LL。

复杂度 O(n*(15)^3*log(k))

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAX_SIZE = 100 + 8;

LL a[MAX_SIZE], bb[MAX_SIZE];
int c[MAX_SIZE];


//n^3*log(m)
const LL MOD = 1e9 + 7;
const LL M_SIZE = 16;
LL mod(LL &x){
    x -= x / MOD * MOD;
}
struct Matrix{
    LL m[M_SIZE][M_SIZE];
    LL N; //¾ØÕóµÄ½×Êý
    void init(){
        memset(m, 0, sizeof m);
    }
    void setOne(){
        init();
        for(int i = 0; i < M_SIZE; i++) m[i][i] = 1;
    }
    Matrix(){
        init();
    }
    Matrix operator*(const Matrix &rhs) const{
        Matrix ret;
        ret.N = N;
        int i, j, k;
        for(k = 0; k <= N; k++){
            for(i = 0; i <= N; i++){
                for(j = 0; j <= N; j++){
                    mod(ret.m[i][j] += m[i][k] * rhs.m[k][j]);
                }
            }
        }
        return ret;
    }
    void print(){
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++)
                cout << m[i][j] << " ";
            cout << endl;
        }
        cout << endl; } }; Matrix res, b; void quickPow(LL index){ //res.print(); //b.print(); while(index){ if(index&1) res = res * b; index >>= 1;
        b = b * b;
    }
}

char s[MAX_SIZE];

int main()
{
    #ifdef LOCAL
    freopen("e.txt", "r", stdin);
    //freopen("e.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, kk;
    cin >> n >> kk;
    res.N = 15;
    b.N = 15;
    res.init();
    res.setOne();
    int i, j, k;
    for(i = 1; i <= n; i++){ cin >> a[i] >> bb[i] >> c[i];
    }

    for(i = 1; i <= n; i++){
        b.init();
        for(j = 0; j <= c[i]; j++){
            if(j+1 <= c[i]) b.m[j][j+1]++; if(j-1 >=0) b.m[j][j-1]++;
            b.m[j][j]++;
        }
        //cout << (bb[i] - a[i] + 1) << endl; if(bb[i] >= kk) quickPow(kk - a[i]);
        else quickPow(bb[i] - a[i]);
    }


    LL ans = res.m[0][0];
    cout << ans << endl;

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx