hdu5607graph
31882 ワード
graph
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
問題の説明
説明の入力
出力の説明
入力サンプル
出力サンプル
Hint
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
問題の説明
N ( 1~n),M , u, , K .
説明の入力
N,M, .
M , X,Y. X Y ( ).
Q, .
Q , u,K, .
N≤50,M≤1000,Q≤20,u≤n,K≤109.
.
出力の説明
Q , N , , i u K i .
, YX , X×Y109+5 mod (109+7) .
, PE.
入力サンプル
3 2
1 2
1 3
1
1 1
出力サンプル
0 500000004 500000004
Hint
, , (1−>2,1−>3). 1 , , 1/2 2, 1/2 3, 0 0.5 0.5
, 1∗2109+5 mod (109+7)=500000004.
t , , . cf
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int n;
struct Matrix{
__int64 m[51][51];
void init(){
memset(m,0,sizeof(m));
}
Matrix operator *(const Matrix &b) const{
Matrix ret;
ret.init();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(m[i][j]!=0){
for(int k=1;k<=n;k++)
ret.m[i][k]=(ret.m[i][k]+m[i][j]*b.m[j][k])%MOD;
}
}
return ret;
}
};
Matrix mat[35],base;
__int64 a[51];
Matrix Pow(int n,int num){
Matrix ans;
ans.init();
Matrix base1;
for(int i=1;i<=num;i++){
ans.m[i][i]=1;
for(int j=1;j<=num;j++)
base1.m[i][j]=base.m[i][j];
}
int cnt=0;
while(n){
if(n&1)
ans=base1*ans; // ,
n>>=1;
base1=base1*base1;
}
return ans;
}
__int64 POW(__int64 n,int m){
__int64 ans=1;
while(m){
if(m&1)
ans=ans*n%MOD;
n=n*n%MOD;
m>>=1;
}
return ans;
}
int u[1001],v[1001];
int degree[51];
int main(){
for(int i=1;i<=50;i++)
a[i]=POW((__int64)i,1000000005);
int m;
while(scanf("%d%d",&n,&m)!=EOF){
base.init();
memset(degree,0,sizeof(degree));
for(int i=1;i<=m;i++){
scanf("%d%d",&u[i],&v[i]);
degree[u[i]]++;
}
for(int i=1;i<=m;i++)
base.m[u[i]][v[i]]=a[degree[u[i]]];
int Q;
scanf("%d",&Q);
int s,k;
while(Q--){
scanf("%d%d",&s,&k);
Matrix ans=Pow(k,n);
for(int i=1;i<=n;i++)
printf("%I64d ",ans.m[s][i]);
printf("
");
}
}
return 0;
}