摘要:邻接矩阵解决图论问题

「TJOI2017」可乐

题面

题目分析

看完题目后脑补了一下邻接矩阵但是不知道怎么用,于是这位没有数理基础的选手打开了题解看性质.

考虑邻接矩阵的性质,比如题中的样例:

它包含了图的联通性的信息,如果将其的信息视为从一个起点走一步达到其他点的方案数,将其自乘一遍便可以得到从一个点走两步达到其他点的方案数:

这启发我们使用矩阵快速幂解决在走$t$步后到达其他点的方案数.

但是题目中还有在一个点停下和在一个点结束的限制,对于在一个点停下,向自己连边即可,对于在一个点结束,向虚点$0$号点连一条有向边即可表示.

最后统计一遍$\sum_{i=0}^{n}a_{1,i}$得到答案.

代码

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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=31,mod=2017;
lxl n,m,t,ans;
struct _Matrix
{
lxl a[big][big];
_Matrix(){memset(a,0,sizeof a);}
inline _Matrix operator *(const _Matrix &another)const
{
_Matrix b;
for(R int i(0);i<big;++i)
for(R int k(0);k<big;++k)
for(R int j(0);j<big;++j)
b.a[i][j]=(b.a[i][j]+a[i][k]*another.a[k][j])%mod;
return b;
}
}edge,I;
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void init()
{
for(R int i(0);i<big;++i)I.a[i][i]=1;
}
inline _Matrix FastPow(_Matrix a,lxl b)
{
_Matrix A=I;
for(;b;b>>=1,a=a*a)if(b&1)A=a*A;
return A;
}
int main(void)
{
init();
n=read(),m=read();
for(R int i(0);i<=n;++i)edge.a[i][i]=1,edge.a[i][0]=1;
for(R int i(1);i<=m;++i)
{
lxl u=read(),v=read();
edge.a[u][v]=edge.a[v][u]=1;
}
t=read();
edge=FastPow(edge,t);
for(R int i(0);i<=n;endl,++i)
for(R int j(0);j<=n;++j)
printf("%lld ",edge.a[i][j]);
for(R int i(0);i<=n;++i)ans=(ans+edge.a[1][i])%mod;
printf("%lld\n",ans);
return 0;
}