CodeForces - 821E Okabe and El Psy Kongroo dp+矩阵快速幂

题目链接

题意:

n条直线(a[i],b[i],c[i]) 表示在x=a[i]~b[i]内 运动的高度0<=y<=c[i],
a[i]=b[i-1],a[1]=0,a[n]<=k<=b[n],一个人有三个运动方向(x+1,y+1),(x+1,y),(x+1,y-1)
n<=100,c[i]<=15, a[i],b[i],k<=1e18 问从(0,0)->(k,0)的方法数?

思路:

首先dp方程很好得到,设dp[i][j]表示从（0,0） -> （i，j）的方法数。
那么有 dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];

然后发现k很大1e18,我们不可能递推过去了. 又观察到n很小,c也很小,又是线性递推转移,可以想到是矩阵快速幂优化的套路题.
但是因为他存在一个上界c,所以我不是很会 = . =

其实这里我们可以将每一条线段单独拿出来做快速幂,即还是构造一个 16*16的矩阵,dp[0][0]=1,每次转移时,因为有上界的影响,每次传一个矩阵的大小,并将超过范围的列向量对应位置清0.

就是相当于,每有一个线段(ai,bi)和对应上界ci ,我们就对这个范围内做快速幂.相当于从x轴0 -> bi 做了一次转移,这样最多一百次.

复杂度O(n∗163∗log1e18)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9+7;
struct matrix 
{
    ll s[20][20];
};
matrix A,B,mid;
matrix qmul(matrix a,matrix b,int len)
{
    matrix ans;
    memset(ans.s,0,sizeof ans.s);
    for(int i = 0;i <= len;++i)
        for(int k = 0;k <= len;++k)
            for(int j = 0;j <= len;++j)
            {
                ans.s[i][j] = (ans.s[i][j] + a.s[i][k]*b.s[k][j]%mod) %mod;
            }
    return ans;
}
matrix qmod(matrix a,ll k,int len)
{
    matrix E;
    memset(E.s,0,sizeof E.s);
    for(int i = 0;i <= len;++i)
    E.s[i][i] = 1;
    while(k)
    {
        if(k&1)
        E=qmul(E,a,len);
        a=qmul(a,a,len);
        k >>= 1;
    }
    return E;
}
int main()
{
    int n;
    ll k;
    while(~scanf("%d %lld",&n,&k))
    {
        memset(mid.s,0,sizeof mid.s);
        memset(A.s,0,sizeof A.s);
        for(int i = 0;i <= 15;++i)
        {
            for(int j = i-1;j <= i + 1 && j <= 15;++j)
            {
                if(j >= 0 &&j <= 15)
                A.s[i][j]=1;
            }

        }
        mid.s[0][0] = 1;
        bool flag = 0;
        for(int i = 1;i <= n;i++)
        {
            ll l,r;
            int y;
            scanf("%lld %lld %d",&l,&r,&y);
            if(r > k) r = k,flag = 1;
            B=qmod(A,r-l,y);
            for(int j = y + 1;j <= 15;++j)//超过上界的要清0 
            {
                mid.s[j][0] = 0;
            }
            B=qmul(B,mid,y);
            for(int j = 0;j <= 15;++j)
            {
                mid.s[j][0] = B.s[j][0];
            }
            if(flag)
            break;
        }
        printf("%lld\n",B.s[0][0]);
    }
    return 0;
}