样例输出 8 , 我的程序输出 5
我调了很长时间也没找出问题来……
很奇怪,求帮我看一看,谢谢!
#include<bits/stdc++.h>
using namespace std;
const int MAXN=35;
const int mod=2017;
inline int read()
{
char c;int res=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=res*10+c-'0';
return res;
}
struct Mat
{
int a[MAXN][MAXN];
int n,m;
Mat(){n=m=0;memset(a,0,sizeof a);}
Mat(int k){n=m=k;memset(a,0,sizeof a);for(int i=0;i<=k;i++)a[i][i]=1;}
Mat(int x,int y){n=x,m=y;memset(a,0,sizeof a);}
Mat operator *(Mat b)
{
Mat c(n,b.m);
for(int i=1;i<=c.n;i++)
{
for(int j=1;j<=c.m;j++)
{
for(int k=1;k<=m;k++)
{
c.a[i][j]=(c.a[i][j]+(a[i][k]*b.a[k][j])%mod)%mod;
}
}
}
return c;
}
Mat operator *=(Mat b)
{
return *this=*this*b;
}
Mat operator ^(int k)
{
Mat ans(n);
Mat base=*this;
while(k)
{
if(k&1) ans*=base;
base*=base;
k>>=1;
}
return ans;
}
Mat operator ^=(int k)
{
return *this=*this^k;
}
};
int N,M,u,v,T,ans;
int main()
{
N=read(),M=read();
Mat G(N);
for(int i=1;i<=M;i++)
{
u=read(),v=read();
G.a[u][v]=1;
G.a[v][u]=1;
}
for(int i=1;i<=N;i++)
{
G.a[i][0]=1;
}
T=read();
G^=T;
for(int i=0;i<=N;i++)
{
ans=(ans+G.a[1][i])%mod;
}
printf("%d\n",ans);
return 0;
}