Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int N = 1e2 + 7, MOD = 1e9 + 9, POW = 31;
- int n, a[N][N], b[N][N];
- int ph_a[N][N], ph_b[N][N];
- int pp[N*N];
- void precalc() {
- pp[0] = 1;
- for(int i = 1; i < N*N; i ++)
- pp[i] = (pp[i-1] * POW) % MOD;
- for(int j = 0; j < n; j ++)
- {
- ph_a[0][j] = a[0][j];
- for(int i = 1; i < n; i ++)
- ph_a[i][j] = (ph_a[i-1][j] + pp[i] * a[i][j]) % MOD;
- }
- for(int j = 0; j < n; j ++)
- {
- ph_b[0][j] = b[0][j];
- for(int i = 1; i < n; i ++)
- ph_b[i][j] = (ph_b[i-1][j] + pp[i] * b[i][j]) % MOD;
- }
- }
- int binpow(int x, int y, int m) {
- if(y == 0)
- return 1;
- if(y % 2)
- return (x * binpow(x, y-1, m)) % m;
- int zz = binpow(x, y/2, m);
- return (zz*zz) % m;
- }
- int gha(int i1, int i2, int j) {
- int cch = (ph_a[i2][j] - (i1?ph_a[i1-1][j]:0) + MOD) % MOD;
- int ts = pp[i1];
- return (cch * binpow(ts, MOD-2, MOD)) % MOD;
- }
- int ghb(int i1, int i2, int j) {
- int cch = (ph_b[i2][j] - (i1?ph_b[i1-1][j]:0) + MOD) % MOD;
- int ts = pp[i1];
- return (cch * binpow(ts, MOD-2, MOD)) % MOD;
- }
- int32_t main()
- {
- srand(time(NULL));
- ios_base::sync_with_stdio(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- cin >> n;
- for(int i = 0; i < n; i ++)
- for(int j = 0; j < n; j ++)
- cin >> a[i][j];
- for(int i = 0; i < n; i ++)
- for(int j = 0; j < n; j ++)
- cin >> b[i][j];
- precalc();
- set<pair<pair<int, int>, pair<int, int> > > sm1, sm2;
- for(int i1 = 0; i1 < n; i1 ++)
- for(int i2 = i1; i2 < n; i2 ++)
- {
- vector<int> shs;
- for(int j = 0; j < n; j ++)
- shs.push_back(gha(i1, i2, j));
- for(int j1 = 0; j1 < n; j1 ++)
- {
- int cpow = 1;
- int chh = 0;
- for(int j2 = j1; j2 < n; j2 ++)
- {
- chh = (chh + shs[j2] * cpow) % MOD;
- cpow = (cpow * pp[i2-i1+1]) % MOD;
- sm1.insert({{0, chh}, {j2 - j1 + 1, i2 - i1 + 1}});
- }
- }
- }
- for(int i1 = 0; i1 < n; i1 ++)
- for(int i2 = i1; i2 < n; i2 ++)
- {
- vector<int> shs;
- for(int j = 0; j < n; j ++)
- shs.push_back(ghb(i1, i2, j));
- for(int j1 = 0; j1 < n; j1 ++)
- {
- int cpow = 1;
- int chh = 0;
- for(int j2 = j1; j2 < n; j2 ++)
- {
- chh = (chh + shs[j2] * cpow) % MOD;
- cpow = (cpow * pp[i2-i1+1]) % MOD;
- sm2.insert({{0, chh}, {j2 - j1 + 1, i2 - i1 + 1}});
- }
- }
- }
- int ans = 0;
- for(auto i : sm1)
- if(*(sm2.find(i)) == i)
- ans++;
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement