【BZOJ4887】[TJOI2017]可乐（矩阵快速幂）

题面

BZOJ

洛谷

题解

模板题？？？

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 35

#define MOD 2017

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

int g[MAX][MAX],n,m,N;

struct Matrix{int s[MAX][MAX];int*operator[](int x){return s[x];}}A,S;

Matrix operator*(Matrix a,Matrix b)

{

	Matrix c;memset(c.s,0,sizeof(c.s));

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

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

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

				c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;

	return c;

}

int main()

{

	n=read();m=read();N=n+1;

	for(int i=1,u,v;i<=m;++i)u=read(),v=read(),A[u][v]+=1,A[v][u]+=1;

	for(int i=1;i<=n;++i)A[i][i]+=1,A[i][N]+=1;A[N][N]+=1;

	for(int i=1;i<=N;++i)S[i][i]=1;

	int T=read();while(T){if(T&1)S=S*A;A=A*A;T>>=1;}

	int ans=0;for(int i=1;i<=N;++i)ans=(ans+S[1][i])%MOD;

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

	return 0;

}