Submission #244965

#	Time	Username	Problem	Language	Result	Execution time	Memory
244965		VEGAnn	Osmosmjerka (COCI17_osmosmjerka)	C++14	140 / 160	4064 ms	29644 KiB

osmosmjerka

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define s2 array<short,2>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 510;
const int M = 100100;
const int x = 233;
const int PW = 233;
const int md = 999999937;
//const int md = 998244353;
//const int md = 988244353;
//const int md = int(1e9) + 9;
//const int md = int(1e9) + 7;
gp_hash_table<int, int> mem;
int n, m, stp[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int hsh[N], xn, a[N][N], big_x, k, po[N * N], lcm, pre[8][N][N], inv, prec[N];
int mlp[N][26], prog;
s2 nt[8][N][N];

int mult(int x, int y) { return (1ll * x * y) % md; }

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int binpow(int x, int po){
    int res = 1;
    while (po > 0){
        if (x & 1)
            res = mult(res, x);
        x = mult(x, x);
        po >>= 1;
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m >> k;

    lcm = n * m / __gcd(n, m);

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        char c; cin >> c;

        a[j][i] = c - 'a' + 1;
    }

    swap(n, m);

    po[0] = 1;

    for (int i = 1; i <= lcm; i++)
        po[i] = mult(po[i - 1], x);

    big_x = binpow(po[lcm], k / lcm);
    inv = binpow(sub(po[lcm], 1), md - 2);
    prog = mult(sub(big_x, 1), inv);

    for (int i = 0; i < n; i++){
        int lst = 0;

        for (int it = 0; it < 26; it++) {
            lst = sum(lst, po[i]);

            mlp[i][it] = lst;
        }
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int it = 0; it < 8; it++){
        int x = i, y = j;

        hsh[0] = 0;

        for (int len = 1; len <= n; len++) {
            hsh[len] = sum(hsh[len - 1], mlp[len - 1][a[x][y] - 1]);

            x += stp[it][0];
            y += stp[it][1];

            if (x < 0) x += n;
            if (y < 0) y += m;
            if (x >= n) x -= n;
            if (y >= m) y -= m;
        }

        pre[it][i][j] = hsh[n];
        nt[it][i][j] = {x, y};
    }

    int vl = lcm / n;

    prec[0] = 1;

    for (int i = 1; i <= vl; i++)
        prec[i] = mult(prec[i - 1], po[n]);

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    for (int it = 0; it < 8; it++){
        int x = i, y = j;

        int ost = k % lcm, hs = 0, ost_hsh = 0;

        for (int lst = 1; lst <= vl; lst++){
            int cur = mult(prec[lst], pre[it][x][y]);

            hs = sum(hs, cur);

            if (ost > 0){
                if (ost < n){
                    int xx = x, yy = y, mlu = prec[lst];

                    while (ost > 0){
                        ost_hsh = sum(ost_hsh, mult(mlu, a[xx][yy]));
                        mlu = mult(mlu, PW);

                        xx += stp[it][0];
                        yy += stp[it][1];

                        if (xx < 0) xx += n;
                        if (yy < 0) yy += m;
                        if (xx >= n) xx -= n;
                        if (yy >= m) yy -= m;

                        ost--;
                    }
                } else {
                    ost -= n;
                    ost_hsh = sum(ost_hsh, cur);
                }
            }

            s2 nw = nt[it][x][y];

            x = nw[0];
            y = nw[1];
        }

        int cnt = k / lcm, rhsh = 0;

        if (cnt > 0)
            rhsh = mult(hs, prog);

        rhsh = sum(rhsh, mult(big_x, ost_hsh));

        mem[rhsh]++;
    }

    ll res = 0;

    for (auto cr : mem){
        ll nw = cr.second;

        nw *= nw;

        res += nw;
    }

    ll full = ll(n) * ll(m) * ll(n) * ll(m) * ll(8) * ll(8);
    ll gc = __gcd(full, res);

    cout << res / gc << "/" << full / gc;

    return 0;
}

Compilation message (stderr)

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:115:29: warning: narrowing conversion of 'x' from 'int' to 'short int' inside { } [-Wnarrowing]
         nt[it][i][j] = {x, y};
                             ^
osmosmjerka.cpp:115:29: warning: narrowing conversion of 'y' from 'int' to 'short int' inside { } [-Wnarrowing]

• Subtask 1: 140 / 160