C++14(g++5.4) 解法, 执行用时: 56ms, 内存消耗: 868K, 提交时间: 2019-04-13 00:09:16

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
const int p=1000000007;
int n,m,k,s,xx,yy;
struct mat{
	long long d[102][102];
}a,g,ans,c;
long long tot;
inline void mul(mat &a,mat &b){
	fo(i,1,n)
		fo(j,1,n){
			c.d[i][j]=0;
			fo(k,1,n) c.d[i][j]+=a.d[i][k]*b.d[k][j]%p;
			c.d[i][j]%=p;
		}
	a=c;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&k,&s);
	fo(i,1,m){
		scanf("%d%d",&xx,&yy);
		a.d[xx][yy]++;
	}
	fo(i,1,n) g.d[i][i]=ans.d[i][i]=1;
	while (k){
		if (k&1) mul(ans,a);
		mul(a,a);
		k>>=1;
	}
	fo(i,1,n)if (i!=s){//i==s!!!
		//printf("%lld\n",ans.d[s][i]);
		tot+=ans.d[s][i];
	}
	tot%=p;
	printf("%lld\n",tot);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 533ms, 内存消耗: 612K, 提交时间: 2020-02-27 11:59:12

#include<bits/stdc++.h>
using namespace std;
int i,j,c=0,n,m,k,s,mod=1e9+7;
struct Matrix
{
	int V[105][105];
	Matrix()
	{
		memset(V,0,sizeof(V));
	}
	Matrix operator* (const Matrix &a)const
	{
		Matrix b;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		for(int k=1;k<=n;k++)
		b.V[i][j]=(b.V[i][j]+(long long)V[i][k]*a.V[k][j])%mod;
		return b;
	}
}G,t;
int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&s);
	while(m--)
	scanf("%d%d",&i,&j),G.V[i][j]++;
	for(i=1;i<=n;i++) t.V[i][i]=1;
	for(;k;G=G*G,k>>=1) if(k&1) t=t*G;
	for(i=1;i<=n;i++) if(i!=s) c=(c+t.V[s][i])%mod;
	printf("%d\n",c);
	return 0;
}