oj.uz

Submission #416749

# Submission time Handle Problem Language Result Execution time Memory
416749 2021-06-02T21:40:37 Z SirCovidThe19th Osmosmjerka (COCI17_osmosmjerka) C++14
160 / 160
 2276 ms 108048 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second

const ll p = 419, m1 = 1e9+7, m2 = 1e9+9;
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};

ll bpow(ll a, ll b, ll mod){
    if (b == 0) return 1;
    ll res = bpow(a, b/2, mod)%mod; if (b%2 == 1) return (((res*res)%mod)*a)%mod; else return (res*res)%mod;
}

int main() {
    
    ll n, m, k; cin >> n >> m >> k; k = min(n*m, k); 
    string grid[n]; map<pair<ll, ll>, ll> eq; 
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int d = 0; d < 8; d++){
        pair<ll, ll> vals[n][m][(int)floor(log2(k))+1], res[n][m]; ll cnt = k; memset(res, 0, sizeof(res));
        for (int l = 0; (1<<l) <= k; l++){
            ll currPow1 = bpow(p, (1<<(l-1)), m1), currPow2 = bpow(p, (1<<(l-1)), m2);
            for (int i = 0; i < n; i++){
                for (int j = 0; j < m; j++){
                    if (l == 0) {vals[i][j][l] = {(grid[i][j]-'a'+1), (grid[i][j]-'a'+1)}; continue;}
                    int r = (i+((1<<(l-1))*di[d])+INT_MAX*n)%n, c = (j+((1<<(l-1))*dj[d])+INT_MAX*m)%m;
                    vals[i][j][l] = {(vals[i][j][l-1].f+vals[r][c][l-1].f*currPow1)%m1,
                                     (vals[i][j][l-1].s+vals[r][c][l-1].s*currPow2)%m2};
                }
            }
            if ((k>>l)%2 == 1){
                cnt -= (1<<l); ll upd1 = bpow(p, cnt, m1), upd2 = bpow(p, cnt, m2);
                for (int i = 0; i < n; i++){
                    for (int j = 0; j < m; j++){
                        int r = (i+(cnt*di[d])+INT_MAX*n)%n, c = (j+(cnt*dj[d])+INT_MAX*m)%m; 
                        res[i][j] = {(res[i][j].f+vals[r][c][l].f*upd1)%m1, 
                                     (res[i][j].s+vals[r][c][l].s*upd2)%m2};
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) eq[res[i][j]]++;
    }
    ll good = 0, tot = (ll)(n*m*8)*(n*m*8);
    for (auto elem : eq) good += elem.s*elem.s; 
    ll div = __gcd(good, tot); cout<<good/div<<"/"<<tot/div;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 5 ms 716 KB Output is correct
6 Correct 42 ms 4828 KB Output is correct
7 Correct 602 ms 35396 KB Output is correct
8 Correct 2276 ms 108048 KB Output is correct