BZOJ-1875 HH去散步 DP+矩阵乘法快速幂

时间：2023-09-18 08:31:38

1875: [SDOI2009]HH去散步

Time Limit: 20 Sec Memory Limit: 64 MB

Submit: 1196 Solved: 553

[Submit][Status][Discuss]

Description

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

Input

第一行：五个整数N，M，t，A，B。其中N表示学校里的路口的个数，M表示学校里的 路的条数，t表示HH想要散步的距离，A表示散步的出发点，而B则表示散步的终点。 接下来M行，每行一组Ai，Bi，表示从路口Ai到路口Bi有一条路。数据保证Ai = Bi，但 不保证任意两个路口之间至多只有一条路相连接。 路口编号从0到N − 1。 同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。 答案模45989。

Output

一行，表示答案。

Sample Input

4 5 3 0 0

0 1

0 2

0 3

2 1

3 2

Sample Output

4

HINT

对于30%的数据，N ≤ 4，M ≤ 10，t ≤ 10。 对于100%的数据，N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B

Source

Day1

其实这题应该不难，但是真的没想到正解....

题解：

正常是对点构造矩阵，那么这里用边来构造，保证走的时候不经过反向边即可，然后矩乘快速幂加速

code:

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int read()

{

    int x=0,f=1; char ch=getchar();

    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define maxn 25

#define maxm 70

#define p 45989

int n,m,t,st,ed;

struct data{int to,next;}edge[maxm*2];

int head[maxm],cnt;

int l,ans;

struct Mat{int a[maxm*2][maxm*2];Mat(){memset(a,0,sizeof(a));}};

void add(int u,int v)

{

    cnt++;

    edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;

}

Mat mul(Mat A,Mat B)

{

    Mat re;

    for (int i=1; i<=l; i++)

        for (int j=1; j<=l; j++)

            for (int k=1; k<=l; k++)

                re.a[i][j]=(re.a[i][j]+(A.a[i][k]*B.a[k][j])%p)%p;

    return re;

}

Mat quick_mul(Mat A,int x)

{

    Mat re;

    for (int i=1; i<=l; i++) re.a[i][i]=1;

    while (x)

        {

            if (x&1) re=mul(re,A);

            x>>=1; A=mul(A,A);

        }

    return re;

}

int findre(int x)

{

    if (x&1) return x+1;

        else return x-1;

}

int main()

{

    n=read(),m=read(),t=read(),st=read(),ed=read();

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

        {

            int u=read(),v=read();

            add(u,v); add(v,u);

        }

    Mat x,y;

    for (int i=head[st]; i; i=edge[i].next)

        x.a[1][i]=1;

    l=cnt;

    if (t==0) {if (st==ed) puts("1"); else puts("0"); return 0;}

    for (int i=1; i<=l; i++)

        for (int j=head[edge[i].to]; j; j=edge[j].next)

            if (j!=findre(i)) y.a[i][j]=1;

    x=mul(x,quick_mul(y,t-1));

    for (int i=head[ed]; i; i=edge[i].next)

        ans=(ans+x.a[1][findre(i)])%p;

    printf("%d\n",ans);

    return 0;

}

相关文章