fork download
copy 
  1. /*
  2. -----------------------------------------------------------------------------
  3. Author :            ---------------------------------------------------------
  4.     UTKAR$H $AXENA  ---------------------------------------------------------
  5.     IIT INDORE      ---------------------------------------------------------
  6. -----------------------------------------------------------------------------
  7. */
  8. #include<bits/stdc++.h>
  9. #include<iostream>
  10. using namespace std;
  11. #define fre 	freopen("0.in","r",stdin),freopen("0.out","w",stdout)
  12. #define abs(x) ((x)>0?(x):-(x))
  13. #define M 1000000007
  14. #define lld signed long long int
  15. #define pp pop_back()
  16. #define ps(x) push_back(x)
  17. #define mpa make_pair
  18. #define pii pair<int,int>
  19. #define fi first
  20. #define se second
  21. #define scan(x) scanf("%d",&x)
  22. #define scanll(x) scanf("%lld",&x)
  23. #define printll(x) printf("%lld\n",x)
  24. #define boost ios_base::sync_with_stdio(0)
  25. //vector<int> g[2*100000+5];int par[2*100000+5];
  26. struct mat
  27. {
  28. 	int m[32][32];
  29. 	int N=30;
  30. 	mat()
  31. 	{
  32. 		for(int i=1;i<=N;++i)
  33. 			for(int j=1;j<=N;++j)
  34. 				m[i][j]=0;
  35. 	}
  36. 	mat(int i)
  37. 	{
  38. 		//identity
  39. 		for(int i=1;i<=N;++i)
  40. 			for(int j=1;j<=N;++j)
  41. 				m[i][j]=0;
  42. 		for(int i=1;i<=N;++i)
  43. 			m[i][i]=1;
  44. 	}
  45. 	 ~mat() { }
  46. }G;
  47. int N;
  48. mat mul(mat a,mat b)
  49. {
  50. 	mat c;
  51. 	for(int i=1;i<=N;++i)
  52. 	{
  53. 		for(int j=1;j<=N;++j)
  54. 		{
  55. 			for(int k=1;k<=N;++k)
  56. 			{
  57. 				c.m[i][j]+=(((lld)a.m[i][k])*b.m[k][j])%M;
  58. 				c.m[i][j]%=M;
  59. 			}
  60. 		}
  61. 	}
  62. 	return c;
  63. }
  64. mat pow(mat base, lld exponent)
  65. {
  66. 	mat result(1);
  67. 	while (exponent > 0)
  68. 	{
  69. 		if (exponent % 2 == 1)
  70. 			result = mul(result , base);
  71. 		exponent = exponent >> 1;
  72. 		base = mul(base , base);
  73. 	}
  74. 	return result;
  75. }
  76. mat add(mat a,mat b)
  77. {
  78. 	for(int i=1;i<=N;++i)
  79. 	{
  80. 		for(int j=1;j<=N;++j)
  81. 		{
  82. 			a.m[i][j]=(a.m[i][j]+b.m[i][j])%M;
  83. 		}
  84. 	}
  85. 	return a;
  86. }
  87. mat rec(lld S)
  88. {
  89. 	if(S==1)
  90. 		return G;
  91. 	if(S%2==1)
  92. 		return add(pow(G,S),rec(S-1));
  93.  
  94. 	mat temp=pow(G,S/2);
  95. 	for(int i=1;i<=N;++i)
  96. 		temp.m[i][i]=(temp.m[i][i]+1)%M;
  97.  
  98. 	return mul(rec(S/2),temp);
  99. }
  100. void print(mat A)
  101. {
  102. 	for(int i=1;i<=N;++i)
  103. 	{
  104. 		for(int j=1;j<=N;++j)
  105. 		{
  106. 			cout<<A.m[i][j]<<'\t';
  107. 		}
  108. 		cout<<endl;
  109. 	}
  110. }
  111. int main()
  112. {
  113. 	lld K;
  114. 	int m,a,b,Q;
  115. 	cin>>N>>m>>K;
  116.  
  117. 	for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)G.m[i][j]=0;
  118.  
  119. 	for(int i=1;i<=m;++i)
  120. 	{
  121. 		scan(a);
  122. 		scan(b);
  123. 		G.m[a][b]+=1;
  124. 	}
  125. 	G=rec(K);
  126. 	cin>>Q;
  127. 	while(Q--)
  128. 	{
  129. 		scan(a);
  130. 		scan(b);
  131. 		printf("%d\n",G.m[a][b]);
  132. 	}
  133. }
  134.  
Runtime error #stdin #stdout 0s 11208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6Riqxn
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!