fork(3) download
copy 
  1. /*
  2. 	Code By : Amrutansu Garanaik
  3. 	codechef id : dragonemperor
  4. */
  5. #include<stdio.h>
  6. #define MOD 1000000007
  7. typedef long long ll;
  8. ll n;
  9. void multiply(ll a[n][n],ll b[n][n])		//multiply a and b and store in a
  10. {
  11. 	ll c[n][n];
  12. 	for(int i=0;i<n;i++)
  13. 	for(int j=0;j<n;j++)
  14. 	{
  15. 		c[i][j]=0;
  16. 		for(int k=0;k<n;k++)
  17. 		{
  18. 			c[i][j]+=a[i][k]*b[k][j];
  19. 			c[i][j]%=MOD;
  20. 		}
  21. 	}
  22. 	for(int i=0;i<n;i++)
  23. 	for(int j=0;j<n;j++)
  24. 		a[i][j]=c[i][j];
  25. }
  26. void expo(ll graph[n][n],ll result[n][n],ll power)
  27. {
  28. 	while(power)
  29. 	{
  30. 		if(power&1)
  31. 			multiply(result,graph);
  32. 		multiply(graph,graph);
  33. 		power>>=1;
  34. 	}
  35. }
  36. int main()
  37. {
  38. 	ll test,e,a,b,q,l;
  39. 	scanf("%lld",&test);
  40. 	while(test--)
  41. 	{
  42. 		scanf("%lld%lld",&n,&e);
  43. 		ll graph[n][n],result[n][n];
  44. 		for(int i=0;i<n;i++)
  45. 		for(int j=0;j<n;j++)
  46. 		{
  47. 			graph[i][j]=0;
  48. 			result[i][j]=0;
  49. 			if(i==j)
  50. 				result[i][j]=1;
  51. 		}
  52. 		while(e--)
  53. 		{
  54. 			scanf("%lld%lld",&a,&b);
  55. 			graph[a][b]++;
  56. 			graph[b][a]++;
  57. 		}
  58.  
  59. 		/*for(int i=0;i<n;i++)
  60. 		{
  61. 			printf("\n");
  62. 			for(int j=0;j<n;j++)
  63. 				printf("%lld\t",result[i][j]);
  64. 		}
  65. 		*/
  66.  
  67. 		scanf("%lld%lld",&q,&l);
  68. 		expo(graph,result,l);
  69.  
  70. 		/*for(int i=0;i<n;i++)
  71. 		{
  72. 			printf("\n");
  73. 			for(int j=0;j<n;j++)
  74. 				printf("%lld\t",result[i][j]);
  75. 		}
  76. 		*/
  77.  
  78. 		while(q--)
  79. 		{
  80. 			scanf("%lld%lld",&a,&b);
  81. 			printf("%lld\n",result[a][b]);
  82. 		}
  83. 	}
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 2060KB
comments (?)
stdin
copy 
1
3 2
0 1
1 2
2 3
0 1
1 2
stdout
copy 
2
2
https://ideone.com/ltZPGD
language:
C99 (gcc 8.3)
created:
8 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!