fork(1) download
  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
stdin
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
553 1323 183 183
477 42 42
427 427
60