【Luogu】P3758可乐（矩阵优化DP）

　　一开始想到这可能能用矩阵优化，但以为暴力就能卡过……T成二十分

　　首先我们回顾一下我们的暴力转移方程

　　用f[i][j][0/1]表示在i时刻，j点，1不爆炸，0已爆炸的方案数，那么f[i][j][0]=f[i-1][j][0]+f[i-1][j][1]，f[i][j][1]=f[i-1][j][1]+f[i-1][k][1]（其中k表示与j相邻的点）。

　　然后我们看f[i][j][1]=f[i-1][j][1]+f[i-1][k][1]这个式子

　　如果设定j和j相连，就化简为f[i][j][1]=f[i-1][k][1]

　　然后就可以用矩阵乘法啦

　　考虑到f[i][j][0]的求法，发现这是一个关于f[i-1][j][1]的和

　　而我们发现f[i-1][j][1]是一串矩阵等比数列

　　于是应用等比数列求和公式

#include<algorithm>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#define mod 2017

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int n,m;

struct Matrix{

    long long s[][];

    Matrix(){memset(s,,sizeof(s));    }

    Matrix operator *(const Matrix &a){

        Matrix ans;

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

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

                for(int k=;k<=n;++k)

                    ans.s[i][j]=(ans.s[i][j]+(s[i][k]*a.s[k][j])%mod)%mod;

        return ans;

    }

    Matrix operator +(const Matrix &a){

        Matrix ans;

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

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

                ans.s[i][j]=(s[i][j]+a.s[i][j])%mod;

        return ans;

    }

};

Matrix Pow(Matrix x,int p){

    Matrix ans;

    for(int i=;i<=n;++i)    ans.s[i][i]=;

    while(p){

        if(p&)    ans=ans*x;

        x=x*x;

        p>>=;

    }

    return ans;

}

Matrix Sum(Matrix x,int p){

    Matrix ans;

    if(!p)    return ans;

    for(int i=;i<=n;++i)    ans.s[i][i]=;

    ans=ans+Pow(x,p>>);    ans=ans*Sum(x,p>>);

    if(p&)    ans=ans+Pow(x,p);

    return ans;

}

int q[][];

Matrix Start;

int ans;

int main(){

    n=read(),m=read();

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

        int from=read(),to=read();

        q[from][to]=q[to][from]=;

    }

    for(int i=;i<=n;++i)    q[i][i]=;

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

        for(int j=;j<=n;++j)    Start.s[i][j]=q[i][j];

    int t=read();

    Matrix now;    now=Pow(Start,t);

    for(int i=;i<=n;++i)    ans=(ans+now.s[i][])%mod;

    Matrix sum;    sum=Sum(Start,t -);

    for(int i=;i<=n;++i)    sum.s[i][i]=(sum.s[i][i]+)%mod;

    for(int i=;i<=n;++i)    ans=(ans+sum.s[i][])%mod;

    printf("%d",ans);

    return ;

}

巴特西

【Luogu】P3758可乐（矩阵优化DP）

最新文章

热门文章