BZOJ 1875: [SDOI2009]HH去散步

Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 2192 Solved: 1110
[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。
N ≤ 20，M ≤ 60，t ≤ 2^30，0 ≤ A,B
Output

一行，表示答案。
Sample Input
4 5 3 0 0

0 1

0 2

0 3

2 1

3 2
Sample Output
4

解题思路

矩阵，不能以点存，要借助边存，把无向边拆成有向边，l记录每条有向边的端点
r记录到达点。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define LL long long

using namespace std;
const int mod = 45989;
const int MAXN = 1005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}

int n,m,st,ed,t;
int l[MAXN<<1],r[MAXN<<1];
LL ans,ar[MAXN<<1];

struct Mat{
    LL a[MAXN][MAXN];
    Mat(){
        memset(a,0,sizeof(a));
    }
    Mat operator *(const Mat &h){
        Mat c;
        for(register int i=0;i<m<<1;i++)
            for(register int j=0;j<m<<1;j++)
                for(register int k=0;k<m<<1;k++)
                    c.a[i][j]=(c.a[i][j]+a[i][k]*h.a[k][j])%mod;
        return c;
    }
}A,B;

inline void fast_pow(Mat x,int y){
    for(;y;y>>=1){
        if(y&1) B=B*x;
        x=x*x;
    }
}

int main(){
    cout<<1<<endl;
    n=rd();m=rd();t=rd();st=rd();ed=rd();
    for(register int i=0;i<m;i++){
        l[i<<1]=r[i<<1|1]=rd();
        r[i<<1]=l[i<<1|1]=rd();
    }
    for(register int i=0;i<m<<1;i++) B.a[i][i]=1;
    for(register int i=0;i<m<<1;i++)
        for(register int j=0;j<m<<1;j++)
            if(l[i]==r[j] && (i^1)!=j) A.a[i][j]=1;
    fast_pow(B,t-1);
    for(register int i=0;i<m<<1;i++)
        for(register int j=0;j<m<<1;j++)
            if(l[j]==st) ar[i]=(ar[i]+B.a[i][j])%mod;
    for(register int i=0;i<m<<1;i++) 
        if(r[i]==ed) ans+=ar[i],ans%=mod;
    printf("%lld",ans);
    return 0;
}