Submission #944841

#	Time	Username	Problem	Language	Result	Execution time	Memory
944841		LonlyR	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	1753 ms	97224 KiB

osmosmjerka

#include<bits/stdc++.h>
#define ii array<int, 2>
#define int long long 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
const int maxn = 505;
int n, m, k, nn, mm;
int st[32][maxn][maxn];
map<int,int> mp;

void make(int dc, int dr)
{
    for (int lg = 1, base = 311; lg < 31; lg++)
    {
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
        {
            int nx = (1ll << (lg - 1)), ny = (1ll << (lg - 1));
            nx = (i + dc * nx + nn) % n;
            ny = (j + dr * ny + mm) % m;
            st[lg][i][j] = st[lg - 1][i][j] * base + st[lg - 1][nx][ny];
        }
        base *= base;
    }
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        int cx = i, cy = j, tmp = 0;
        for (int lg = 0, base = 311; lg < 31; lg++)
        {
            if (k >> lg & 1)
            {
                int nx = (1ll << lg), ny = (1ll << lg);
                tmp = tmp * base + st[lg][cx][cy];
                cx = (cx + dc * nx + nn) % n;
                cy = (cy + dr * ny + mm) % m;
            }
            base *= base;
        }
        mp[tmp]++;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m >> k;
    nn = n * (int)1e9;
    mm = m * (int)1e9;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    {
        char c;
        cin >> c;
        st[0][i][j] = c - 'a' + 1;
    }
    for (int x = -1; x < 2; x++)
        for (int y = -1; y < 2; y++)
            if (!(x == y && x == 0))
                make(x, y);
    int x = 0, y = (n * m * 8) * (n * m * 8);
    for (auto p : mp) x += p.second * p.second;
    int g = __gcd(x, y);
    cout << x / g << "/" << y / g;
}

• Subtask 1: 160 / 160