P3758 [TJOI2017]可乐

https://www.luogu.org/problemnew/show/P3758

设现在有一个邻接矩阵A
不难发现A^k的第i行第j列的数字含义是从i到j经过k步的路径方案总数

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int read(){
    char ch=getchar(); int w=1,c=0;
    for (;!isdigit(ch);ch=getchar()) if (ch==‘-‘) w=-1;
    for (;isdigit(ch);ch=getchar()) c=(c<<3)+(c<<1)+(ch^48);
    return w*c;
}
const int mod=2017;
int n,m,t;
struct Matrix{
	int a[31][31];
	Matrix() {memset(a,0,sizeof a); }
	Matrix operator *(const Matrix &b) const {
		Matrix ret;
		for (int i=0;i<=n;i++)
		for (int j=0;j<=n;j++)
		for (int k=0;k<=n;k++)
		ret.a[i][j]=(ret.a[i][j]+a[i][k]*b.a[k][j])%mod;
		return ret;
	}
}base,ans;
int main(){
	n=read(); m=read();
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		base.a[x][y]=base.a[y][x]=1;
	}
	t=read();
	for (int i=0;i<=n;i++){
		base.a[i][0]=1;
		base.a[i][i]=1;
	}
	ans.a[1][1]=1;
	for (;t;t>>=1,base=base*base)
	if (t&1) ans=ans*base;
	int A=0;
	for (int i=0;i<=n;i++) {
		A=(A+ans.a[1][i])%mod;
	}
	cout<<A<<"\n";
    return 0;
}