fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 101
  5. const int MOD = 1e9 + 7;
  6. struct Matrix
  7. {
  8. 	unsigned long long M[MAX][MAX];
  9. 	Matrix operator * (Matrix &a) 
  10. 	{
  11. 		Matrix ans;
  12. 		memset(ans.M, 0, sizeof ans.M);
  13. 		for(int i = 0; i < MAX; i++)
  14. 			for(int j = 0; j < MAX; j++)
  15. 				for(int k = 0; k < MAX; k++)
  16. 					ans.M[i][j] = (ans.M[i][j] + (M[i][k] * a.M[k][j]) % MOD) % MOD;
  17. 		return ans;
  18. 	}
  19. 	Matrix pow(int p)
  20. 	{
  21. 		Matrix ans, b = *this;
  22. 		for(int i = 0; i < MAX; i++)
  23. 			for(int j = 0; j < MAX; j++)
  24. 			ans.M[i][j] = (i == j);
  25. 		while(p)
  26. 		{
  27. 			if(p & 1)
  28. 			ans = ans * b;
  29. 			p >>= 1;
  30. 			b = b * b;
  31. 		}
  32. 		return ans;
  33. 	}
  34. };
  35.  
  36. int main() {
  37. 	ios_base::sync_with_stdio(false);
  38. 	cin.tie(0);
  39. 	cout.tie(0);
  40. 	int n,r,k,x,y;
  41. 	cin>>n>>r>>k;
  42. 	Matrix m;
  43. 	for(int i=0;i<r;i++)
  44. 	{
  45. 		cin>>x>>y;
  46. 		m.M[x-1][y-1]+=1LL;
  47. 		m.M[y-1][x-1]+=1LL;
  48. 	}
  49. 	m=m.pow(k);
  50. 	for(int i=0;i<n;i++)
  51. 	{
  52. 		for(int j=i+1;j<n;j++)
  53. 		{
  54. 			if(j!=i+1)
  55. 				cout<<" ";
  56. 			if(m.M[i][j]==0)
  57. 				cout<<-1;
  58. 			else
  59. 				cout<<m.M[i][j];
  60. 		}
  61.  
  62. 		cout<<"\n";
  63. 	}
  64.  
  65. 	return 0;
  66. }
Success #stdin #stdout 0.01s 16328KB
comments (?)
stdin
copy 
5 13 4
3 2
5 2
1 2
2 4
1 2
2 3
2 3
2 3
3 2
2 1
1 3
2 3
3 2
stdout
copy 
553 1323 183 183
477 42 42
427 427
60
https://ideone.com/FvMNbo
language:
C++14 (gcc 8.3)
created:
6 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!