Submission #713321

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713321	2023-03-21T16:58:40 Z	Johann	Osmosmjerka (COCI17_osmosmjerka)	C++14	160 / 160	3698 ms	87380 KB

osmosmjerka

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<pii> vpii;
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()

const ll MOD = ((1LL << 61) - 1);
const ll P = 9973;
const ll P1 = 98999;
const ll P2 = 22573;
const ll P3 = 1367;
const ll P4 = 41809;

ll mod_mul(ll a, ll b)
{
    __int128 res = (__int128)a * b;
    return res % MOD;
}

int N, M, K;
vpii dirs = {{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
int shift(int idx, int didx, int amount, int m)
{
    return (((idx + didx * amount) % m) + m) % m;
}
vvi grid;
vvvi dp;
vi pot;
int logheight;

void initDPvars()
{
    logheight = ceil(log2(K) + 1);
    dp.assign(N, vvi(M, vi(logheight, 0)));
    pot.assign(logheight, P); // pot[i] = P^(2^i)
    for (int l = 1; l < logheight; ++l)
        pot[l] = mod_mul(pot[l - 1], pot[l - 1]);
}

void makeDP(int di, int dj)
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            dp[i][j][0] = grid[i][j];

    for (int l = 1; l < logheight; ++l)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                dp[i][j][l] = (dp[i][j][l - 1] + mod_mul(pot[l - 1], dp[shift(i, di, 1 << (l - 1), N)][shift(j, dj, 1 << (l - 1), M)][l - 1])) % MOD;
}

ll lift(int i, int j, int di, int dj, int k)
{
    ll ans = 0;
    ll pp = 1;
    for (int l = 0; l < sz(dp[i][j]); ++l)
    {
        if (k & (1 << l))
        {
            ans = (ans + mod_mul(pp, dp[i][j][l])) % MOD;
            pp = mod_mul(pp, pot[l]);
            i = shift(i, di, 1 << l, N);
            j = shift(j, dj, 1 << l, M);
        }
    }
    return ans;
}

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

    cin >> N >> M >> K;

    grid.assign(N, vi(M, 0));
    for (int i = 0; i < N; ++i)
    {
        string tmp;
        cin >> tmp;
        for (int j = 0; j < M; ++j)
            grid[i][j] = tmp[j];
    }

    initDPvars();

    vi paths;
    for (int di = -1; di <= 1; ++di)
        for (int dj = -1; dj <= 1; ++dj)
        {
            if (di == 0 && dj == 0)
                continue;
            makeDP(di, dj);
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < M; ++j)
                    paths.push_back(lift(i, j, di, dj, K));
        }
    sort(all(paths));

    ll num = 0;
    ll denom = sz(paths) * sz(paths);

    ll last = paths.front();
    ll cnt = 1;
    for (int i = 1; i < sz(paths); ++i)
    {
        if (paths[i] == last)
            ++cnt;
        else
        {
            num += cnt * cnt;
            cnt = 1;
            last = paths[i];
        }
    }
    num += cnt * cnt;

    ll g = __gcd(num, denom);

    cout << num / g << "/" << denom / g << endl;

    return 0;
}

Subtask #1

160.0 / 160.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 ms	340 KB	Output is correct
5	Correct	13 ms	888 KB	Output is correct
6	Correct	77 ms	2828 KB	Output is correct
7	Correct	942 ms	20600 KB	Output is correct
8	Correct	3698 ms	87380 KB	Output is correct