Codeforces Round #420 (Div. 2)

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

题意：起初在(0,0)，现在要求走到(k,0)，问你存在多少种走法。其中有n条线段，每条线段为(a,y)->(b,y)，代表如果x坐标走到[a,b]之间时，处于的y坐标要小于这个线段的y坐标，就是只能在线段的下方走(包括刚好在线段上)，并且前一个段线段的x坐标与后一个线段的x坐标相同。

思路：dp[i][j]代表从起点走到(i,j)时的走法，那么dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1]。由于dp[i]只由dp[i-1]转移过来，所以可以忽略i这一维，由于y坐标比较少，x坐标比较大，所以通过矩阵快速幂来优化。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<vector>

#include<time.h>

#include<stack>

#include<cmath>

using namespace std;

typedef long long int LL;

const LL INF = ;

const int MAXN =  + ;

const int MAXX =  + ;

const int mod = 1e9 + ;

struct Node{

    LL l, r, y;

}P[MAXN];

struct Matrix{

    int row, col;

    LL m[MAXX][MAXX];

    void init(int row, int col){

        this->row = row;

        this->col = col;

        for (int i = ; i < row; ++i)

            for (int j = ; j < col; ++j)

                m[i][j] = ;

    }

}C;

Matrix operator*(const Matrix & a, const Matrix& b){

    Matrix res;

    res.init(a.row, b.col);

    for (int k = ; k < a.col; ++k){

        for (int i = ; i < res.row; ++i){

            if (a.m[i][k] == ) continue;

            for (int j = ; j < res.col; ++j){

                if (b.m[k][j] == ) continue;

                res.m[i][j] = (a.m[i][k] * b.m[k][j] + res.m[i][j]) % mod;

            }

        }

    }

    return res;

}

Matrix operator+(const Matrix & a, const Matrix& b){

    Matrix res;

    res.init(a.row, b.col);

    for (int i = ; i< a.col; ++i){

        for (int j = ; j < res.row; ++j){

            res.m[i][j] = (a.m[i][j] + b.m[i][j]) % mod;

        }

    }

    return res;

}

Matrix Mpow(Matrix A, LL n){

    Matrix ans = A, p = A;

    while (n){

        if (n & ){

            ans = ans*p; n--;

        }

        n >>= ; p = p*p;

    }

    return ans;

}

int main(){

//#ifdef kirito

//    freopen("in.txt", "r", stdin);

//    freopen("out.txt", "w", stdout);

//#endif

//    int start = clock();

    int n; LL k;

    while (~scanf("%d%lld",&n,&k)){

        for (int i = ; i < n; i++){

            scanf("%lld%lld%lld", &P[i].l, &P[i].r, &P[i].y);

        }

        C.init(, );  C.m[][] = ;

        for (int i = ; i < n; i++){

            if (P[i].l >= k){

                break;

            }

            Matrix res; res.init(, );

            for (int j = ; j < ; j++){

                if (j>P[i].y){

                    break;

                }

                for (int q = -; q <= ; q++){

                    if (j + q >=  && j + q <= P[i].y){

                        res.m[j][j + q] = ;

                    }

                }

            }

            res = Mpow(res, min(k,P[i].r) - min(k,P[i].l)-); //超过k的不需计算

            for (int j = P[i].y + ; j < ; j++){ //超过线段y坐标的走法不存在，置0

                C.m[j][] = ;

            }

            C = C*res;

        }

        printf("%lld\n", C.m[][]);

    }

//#ifdef LOCAL_TIME

//    cout << "[Finished in " << clock() - start << " ms]" << endl;

//#endif

    return ;

}

巴特西

Codeforces Round #420 (Div. 2) - E

最新文章

热门文章