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

题目链接：http://codeforces.com/contest/821/problem/E

题意：我们现在位于（0,0）处，目标是走到（K，0）处。每一次我们都可以从（x，y）走到（x+1，y-1）或者（x+1，y）或者（x+1，y+1）三个位子之一。

现在一共有N段线段，每条线段都是平行于X轴的。我们如果此时x是在这段线段之内的话，我们此时走到的点（x，y）需要满足0<=y<=Ci.

现在保证一段线段的终点，一定是下一段线段的起点。问我们从起点走到终点的行走方案数。

题解：简单的dp+矩阵快速幂的模版

显然如果k很小是个很简单的dp,dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1]。但是k很大所以就要用到矩阵快速幂，一般像这种递推方程式都是可以化为用矩阵来求的

dp[1]　　110000000000000　　predp[1]

dp[2]　　111000000000000　　predp[2]

dp[3]　　011100000000000　　predp[3]

dp[4]　　001110000000000　　predp[4]

dp[15]　 000000000000011　　predp[15]

#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 1000000007
using namespace std;
typedef long long ll;
struct Matrix {
    ll dp[17][17];
};
Matrix Mul(Matrix a , Matrix b , ll Max) {
    Matrix c;
    memset(c.dp , 0 , sizeof(c.dp));
    for(ll i = 0 ; i <= Max ; i++) {
        for(ll j = 0 ; j <= Max ; j++) {
            for(int k = 0 ; k <= Max ; k++) {
                c.dp[i][j] += ((a.dp[i][k]) % mod * (b.dp[k][j]) % mod) % mod;
                c.dp[i][j] %= mod;
            }
        }
    }
    return c;
}
Matrix Matrix_quick_pow(Matrix a , ll k , ll Max) {
    Matrix res;
    memset(res.dp , 0 , sizeof(res.dp));
    for(ll i = 0 ; i <= Max ; i++) res.dp[i][i] = 1;
    while(k) {
        if(k & 1) res = Mul(res , a , Max);
        k >>= 1;
        a = Mul(a , a , Max);
    }
    return res;
}
int main() {
    ll n , k;
    scanf("%lld%lld" , &n , &k);
    Matrix ans , ope , pre;
    memset(ope.dp , 0 , sizeof(ope.dp));
    memset(pre.dp , 0 , sizeof(pre.dp));
    for(int i = 0 ; i < 16 ; i++) {
        if(i == 0) {
            ope.dp[i][i] = 1;
            ope.dp[i][i + 1] = 1;
        }
        else if(i == 15) {
            ope.dp[i][i] = 1;
            ope.dp[i][i - 1] = 1;
        }
        else {
            ope.dp[i][i] = 1;
            ope.dp[i][i + 1] = 1;
            ope.dp[i][i - 1] = 1;
        }
    }
    pre.dp[0][0] = 1;
    for(int i = 1 ; i <= n ; i++) {
        ll a , b , Max , flag = 0;
        scanf("%lld%lld%lld" , &a , &b , &Max);
        if(b > k) {b = k , flag = 1;}
        ans = Matrix_quick_pow(ope , b - a , Max);
        for(ll j = Max + 1 ; j < 16 ; j++) pre.dp[j][0] = 0;
        ans = Mul(ans , pre , Max);
        for(ll j = 0 ; j <= Max ; j++) {
            pre.dp[j][0] = ans.dp[j][0];
        }
        if(flag) break;
    }
    printf("%lld
" , ans.dp[0][0]);
    return 0;
}

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

相关推荐