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\n" , ans.dp[0][0]);

    return 0;

}

巴特西

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

最新文章

热门文章