oj.uz

답안 #944841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944841 2024-03-13T06:36:47 Z LonlyR Osmosmjerka (COCI17_osmosmjerka) C++17
160 / 160
 1753 ms 97224 KB 
#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.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 61784 KB Output is correct
2 Correct 7 ms 62044 KB Output is correct
3 Correct 8 ms 62040 KB Output is correct
4 Correct 8 ms 62044 KB Output is correct
5 Correct 13 ms 62300 KB Output is correct
6 Correct 46 ms 64744 KB Output is correct
7 Correct 529 ms 81364 KB Output is correct
8 Correct 1753 ms 97224 KB Output is correct