【BZOJ】1875: [SDOI2009]HH去散步 矩阵快速幂

时间：2023-03-09 07:53:12
【BZOJ】1875: [SDOI2009]HH去散步 矩阵快速幂

【题意】给定n个点m边的无向图，求A到B恰好经过t条边的路径数，路径须满足每条边都和前一条边不同。n<=20,m<=60,t<=2^30。

【算法】矩阵快速幂

【题解】将图的邻接矩阵进行矩阵快速幂就可以得到恰好经过t条边的路径数，但不能满足题目要求。

改为对原图的边进行相互连边，将经过同一个点的边两两连边，这样就是新邻接矩阵的t-1步。

为了满足题目要求，当两条边互为反向边时不连边即可。

最后乘上从A出发的边的矩阵，然后统计到达B的路径数。

复杂度O((m*2)^3 log t)。

#include<cstdio>

#include<cstring>

const int maxn=,MOD=;

int n,m,t,A,B,a[maxn][maxn],ans[maxn][maxn],c[maxn][maxn],tot=,first[maxn];

struct edge{int v,from;}e[maxn];

void multply(int a[maxn][maxn],int b[maxn][maxn]){

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

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

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

            for(int j=;j<=n;j++)c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)a[i][j]=c[i][j];

}

void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

int main(){

    scanf("%d%d%d%d%d",&n,&m,&t,&A,&B);A++;B++;

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

        int u,v;

        scanf("%d%d",&u,&v);

        insert(++u,++v);insert(v,u);

    }

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

        for(int j=first[e[i].v];j;j=e[j].from)if(i!=(j^)){

            a[i][j]++;

        }

    }

    for(int i=first[A];i;i=e[i].from)a[][i]++;//

    n=tot;

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

    while(t){

        if(t&)multply(ans,a);

        multply(a,a);

        t>>=;

    }

    int ANS=;

    for(int i=first[B];i;i=e[i].from)ANS=(ANS+ans[][i^])%MOD;

    printf("%d",ANS);

    return ;

}

相关文章