BZOJ-1875: [SDOI2009]HH去散步

[文章目录]

Description

HH有个一成不变的习惯,喜欢饭后百步走。所谓百步走,就是散步,就是在一定的时间 内,走过一定的距离。 但是同时HH又是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为HH是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多 少种散步的方法。 现在给你学校的地图(假设每条路的长度都是一样的都是1),问长度为t,从给定地点A走到给定地点B共有多少条符合条件的路径,N ≤ 20,M ≤ 60,t ≤ 2^30,0 ≤ A,B

t那么大,显然矩乘。由于不能回头走,所以我们把边设为状态。dp[i][j]表示i时刻走了j这条边的方案数。矩乘加速第一维即可。时间复杂度O()

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=45989;
int n,m,l,s,t;
int head[30],to[200],nxt[200],cnt=1;
inline void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
struct matrix1
{
    int a[130][130];
    matrix1(){memset(a,0,sizeof a);}
    matrix1 operator * (const matrix1 &z)const 
    {
        matrix1 re;
        for(int i=2;i<=cnt;++i)
            for(int j=2;j<=cnt;++j)
                for(int k=2;k<=cnt;++k)
                    re.a[i][j]=(re.a[i][j]+a[i][k]*z.a[k][j])%mod;
        return re;
    }
};
struct matrix2
{
    int a[130];
    matrix2(){memset(a,0,sizeof a);}
    matrix2 operator * (const matrix1 &z)const 
    {
        matrix2 re;
        for(int i=2;i<=cnt;++i)
            for(int j=2;j<=cnt;++j)
                re.a[i]=(re.a[i]+a[j]*z.a[j][i])%mod;
        return re;
    }
};
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&l,&s,&t);
    int x,y;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    matrix1 I;
    for(int i=2;i<=cnt;++i)
        for(int j=head[to[i]];j;j=nxt[j]) if(j!=(i^1))
            I.a[i][j]=1;
    matrix2 ans;
    for(int i=head[s];i;i=nxt[i]) ans.a[i]=1;
    l--;
    while(l)
    {
        if(l&1) ans=ans*I;
        I=I*I; l>>=1;
    }
    int fna=0;
    for(int i=head[t];i;i=nxt[i])
        fna=(fna+ans.a[i^1])%mod;
    printf("%d",fna);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注