Advertisement
Guest User

Untitled

a guest
Apr 26th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 1e2 + 7, MOD = 1e9 + 9, POW = 31;
  6.  
  7. int n, a[N][N], b[N][N];
  8. int ph_a[N][N], ph_b[N][N];
  9. int pp[N*N];
  10.  
  11. void precalc() {
  12. pp[0] = 1;
  13. for(int i = 1; i < N*N; i ++)
  14. pp[i] = (pp[i-1] * POW) % MOD;
  15.  
  16. for(int j = 0; j < n; j ++)
  17. {
  18. ph_a[0][j] = a[0][j];
  19. for(int i = 1; i < n; i ++)
  20. ph_a[i][j] = (ph_a[i-1][j] + pp[i] * a[i][j]) % MOD;
  21. }
  22. for(int j = 0; j < n; j ++)
  23. {
  24. ph_b[0][j] = b[0][j];
  25. for(int i = 1; i < n; i ++)
  26. ph_b[i][j] = (ph_b[i-1][j] + pp[i] * b[i][j]) % MOD;
  27. }
  28. }
  29.  
  30. int binpow(int x, int y, int m) {
  31. if(y == 0)
  32. return 1;
  33. if(y % 2)
  34. return (x * binpow(x, y-1, m)) % m;
  35. int zz = binpow(x, y/2, m);
  36. return (zz*zz) % m;
  37. }
  38.  
  39. int gha(int i1, int i2, int j) {
  40. int cch = (ph_a[i2][j] - (i1?ph_a[i1-1][j]:0) + MOD) % MOD;
  41. int ts = pp[i1];
  42. return (cch * binpow(ts, MOD-2, MOD)) % MOD;
  43. }
  44.  
  45. int ghb(int i1, int i2, int j) {
  46. int cch = (ph_b[i2][j] - (i1?ph_b[i1-1][j]:0) + MOD) % MOD;
  47. int ts = pp[i1];
  48. return (cch * binpow(ts, MOD-2, MOD)) % MOD;
  49. }
  50.  
  51. int32_t main()
  52. {
  53. srand(time(NULL));
  54. ios_base::sync_with_stdio(0);
  55. //freopen("input.txt", "r", stdin);
  56. //freopen("output.txt", "w", stdout);
  57. cin >> n;
  58. for(int i = 0; i < n; i ++)
  59. for(int j = 0; j < n; j ++)
  60. cin >> a[i][j];
  61. for(int i = 0; i < n; i ++)
  62. for(int j = 0; j < n; j ++)
  63. cin >> b[i][j];
  64. precalc();
  65. set<pair<pair<int, int>, pair<int, int> > > sm1, sm2;
  66. for(int i1 = 0; i1 < n; i1 ++)
  67. for(int i2 = i1; i2 < n; i2 ++)
  68. {
  69. vector<int> shs;
  70. for(int j = 0; j < n; j ++)
  71. shs.push_back(gha(i1, i2, j));
  72. for(int j1 = 0; j1 < n; j1 ++)
  73. {
  74. int cpow = 1;
  75. int chh = 0;
  76. for(int j2 = j1; j2 < n; j2 ++)
  77. {
  78. chh = (chh + shs[j2] * cpow) % MOD;
  79. cpow = (cpow * pp[i2-i1+1]) % MOD;
  80. sm1.insert({{0, chh}, {j2 - j1 + 1, i2 - i1 + 1}});
  81. }
  82. }
  83. }
  84. for(int i1 = 0; i1 < n; i1 ++)
  85. for(int i2 = i1; i2 < n; i2 ++)
  86. {
  87. vector<int> shs;
  88. for(int j = 0; j < n; j ++)
  89. shs.push_back(ghb(i1, i2, j));
  90. for(int j1 = 0; j1 < n; j1 ++)
  91. {
  92. int cpow = 1;
  93. int chh = 0;
  94. for(int j2 = j1; j2 < n; j2 ++)
  95. {
  96. chh = (chh + shs[j2] * cpow) % MOD;
  97. cpow = (cpow * pp[i2-i1+1]) % MOD;
  98. sm2.insert({{0, chh}, {j2 - j1 + 1, i2 - i1 + 1}});
  99. }
  100. }
  101. }
  102. int ans = 0;
  103. for(auto i : sm1)
  104. if(*(sm2.find(i)) == i)
  105. ans++;
  106. cout << ans << endl;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement