T2（矩阵快速幂）:

Luogu点我！

BZOJ点我！

T2:

A7MAd1.md.png

A7MSRU.png

数据范围就是矩阵快速幂不解释。

这题与P4159 [SCOI2009]迷路很类似，就是多了限制条件，也少了一些条件。

少了是边的权值变得只有1这一种权值。

多了不能 A->B->A 这种的走法。

如果没有限制走法，那么就是裸矩阵快速幂，只要将每个点看做矩阵上的元素，进行矩阵幂运算即可。

$ ft[i][j] = \sum{k=1}^{n} f{t-1}[i][k] \times f{t-1}[k][j] $

也就是裸的矩阵乘法。

但是限制了一条边走过之后不能立马走回来。

那只要将矩阵中的点换成边即可:

$f_i[i][j]$ 表示从 第i条边的起点 走到 第j条边的终点的方案数。

那就可以解决这个问题了。

upd:

问：为什么第65行的地方需要建立一条虚边？

答：因为否则最终统计答案的时候不能确定从哪一条边的起点到终点的方案数了。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<cstring>
#define R register
#define LL long long
#define Set(s,v) memset(s,v,sizeof(s))

inline LL read(){
    LL ans=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<3)+(ans<<1)+(ch-48);ch=getchar();}
    return ans*f;
}
void write(LL x){
    if(x<0){putchar('-');x=-x;}
    if(x>9){write(x/10);}
    putchar(x%10|48);
}
const int MOD=45989;
struct mat{
    LL x[155][155];
}s,f;
LL ans;
int n,m,t,st,ed;
int x[128],y[128],cnt;
void debug(mat x){
    printf("DEBUG:\n");
    for (int i=1;i<=cnt;++i){
        for (int j=1;j<=cnt;++j){
            printf("%d ",x.x[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
mat mul(mat A,mat B){
    mat res;
    Set(res.x,0);
    for (R int i=1;i<=cnt;++i){
        for (R int k=1;k<=cnt;++k)
            if(A.x[i][k]){
                for (R int j=1;j<=cnt;++j){
                    res.x[i][j]=res.x[i][j]+(A.x[i][k]*B.x[k][j])%MOD;
                }
            }
        for (R int j=1;j<=cnt;++j) res.x[i][j]%=MOD;
    }
    return res;
}
mat mksm(mat a,LL b){
    mat res=s,base=a;
    while(b){
        if(b&1){
            res=mul(res,base);
        }
        base=mul(base,base);
        b>>=1;
    }
    return res;
}
int main(){
    freopen("desire.in","r",stdin);
    freopen("desire.out","w",stdout);
    n=read();m=read();t=read();st=read();ed=read();
    ++st;++ed;
    ++cnt;x[cnt]=0;y[cnt]=st;
    for (R int i=1;i<=m;++i){
        int u=read(),v=read();
        ++u,++v;
        ++cnt;x[cnt]=u;y[cnt]=v;
        ++cnt;x[cnt]=v;y[cnt]=u;
    }
    for (R int i=1;i<=cnt;++i){
        s.x[i][i]=1;
    }
    for (R int i=1;i<=cnt;++i){
        for (R int j=1;j<=cnt;++j){
            if(i==j||i==(j^1)||y[i]!=x[j]){
                continue;
            }else{
                f.x[i][j]=1;//从标号为i的边的起点走到标号为j的边的终点的方案数。 
            }
        }
    }
//    printf("!!%d\n",cnt);
//    debug(f);
//    getchar();
    f=mksm(f,t);
    for (R int i=1;i<=cnt;++i){
        if(y[i]==ed){
            ans=(ans+f.x[1][i])%MOD;
        }
    }
    write(ans);
    puts("");
    return 0;
}