Submission #416128

#	Time	Username	Problem	Language	Result	Execution time	Memory
416128		SirCovidThe19th	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	1532 ms	33512 KiB

osmosmjerka

#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long

const ll p1 = 1663, p2 = 5953, mod = 1e9+7;

//left, right, up, down, up left, up right, down right, down left
int n, m, k; string grid[500];
int di[8] = {0, 0, -1, 1, -1, -1, 1, 1}, dj[8] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll pow1 = 1, pow2 = 1; map<pair<ll, ll>, ll> eq;

bool in1(int i, int j) { return i >= 0 and i < n and j >= 0 and j < m; }
bool in2(int i, int j, int d) { return in1(i-(k-1)*di[d], j-(k-1)*dj[d]); }
void solve(int ti, int tj, int move, int d){
    for (; in1(ti, tj); ti += di[move], tj += dj[move]){
        ll hash1 = 0, hash2 = 0;
        for (int i = ti, j = tj, cnt = 1; cnt <= k or in2(i, j, d); i += di[d], j += dj[d], cnt++){
            ll curr = grid[(i+500*n)%n][(j+500*m)%m]-'a'+1;
            hash1 = ((hash1*p1)+(curr))%mod; hash2 = ((hash2*p2)+(curr))%mod;
            if (cnt > k){
                hash1 = (hash1-(pow1*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
                hash2 = (hash2-(pow2*(grid[i-k*di[d]][j-k*dj[d]]-'a'+1)%mod)+mod)%mod;
            }
            if (cnt >= k)
                eq[{hash1, hash2}]++;
        }
    }
}

int main() {

    cin >> n >> m >> k; k = min(k, max(n, m)*8);
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int i = 0; i < k; i++) pow1 = (pow1*p1)%mod, pow2 = (pow2*p2)%mod;

    solve(0, 0, 1, 7); solve(0, 0, 1, 6); solve(n-1, 0, 1, 4); solve(n-1, 0, 1, 5);
    solve(n-2, 0, 2, 5); solve(n-2, m-1, 2, 4); solve(1, 0, 3, 6); solve(1, m-1, 3, 7);
    solve(0, 0, 1, 3); solve(n-1, 0, 1, 2); solve(0, 0, 3, 1); solve(0, m-1, 3, 0);

    ll good = 0, tot = (ll)(n*m*8)*(n*m*8);
    for (auto elem : eq) good += elem.second*elem.second; 
    ll div = __gcd(good, tot); cout<<good/div<<"/"<<tot/div;
}

• Subtask 1: 160 / 160