Submission #429349

#	Time	Username	Problem	Language	Result	Execution time	Memory
429349		gaussianprimes	Osmosmjerka (COCI17_osmosmjerka)	C++17	80 / 160	4065 ms	6204 KiB

osmosmjerka

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

ll P = 9973;
ll MOD = 1e9+7;
ll poly[(int)5e2][(int)5e2];
ll ppow[(int)5e2];
int M,N,K;

//can't simulate the K-length string, need to stop when it hits origin again
//cycle must be in less than NM steps (think of movement as a permutation function)
//have hashmap using hashes as keys & count # of hashes

//TIME COMPLEXITY: O(8MN*MN)

//denom = (MN*8)^2
//numerator = sum (freq[i])^2
//then divide by gcd

ll gcd(ll x, ll y){
    if (x>y){
        swap(x,y);
    }
    if (x == 0){
        return y;
    }else{
        return gcd(x,y%x);
    }
    //y >= x always

}
int main() {
    cin >> M >> N >> K;

    string s[M];

    for (int i = 0; i < M; i++){
        cin >> s[i];
    }

    unordered_map<ll, ll> count;
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            int curX = i;
            int curY = j;

            for (int dx = -1; dx <= 1; dx++){
                for (int dy = -1; dy <= 1; dy++){
                    if (dx == 0 && dy == 0){
                        continue;
                    }

                    ll rollHash = (s[i][j]-'a');
                    while(true) {
                        curX = (curX + dx+M) % M;
                        curY = (curY + dy+N) % N;

                        rollHash = (rollHash*P+(s[curX][curY]-'a')+MOD)%MOD;
                        //will always end in lcm(M,N) moves so all hashes are of same-length string
                        if (curX == i && curY == j){
                            if (count.count(rollHash)==1) {
                                count[rollHash] += 1;
                            }else{
                                count[rollHash] = 1;
                            }
                            break;
                        }
                    }
                }
            }
        }
    }

    ll num = 0;
    for (auto e: count){
        num += e.second*e.second;
    }
    ll denom = (8*M*N)*(8*M*N);

    ll g = gcd(num, denom);

    num = num/g;
    denom = denom/g;

    cout << num << "/" << denom;

    return 0;
}

• Subtask 1: 80 / 160