제출 #1355033

#제출 시각아이디문제언어결과실행 시간메모리
1355033vjudge1Osmosmjerka (COCI17_osmosmjerka)C++20
40 / 160
1584 ms96292 KiB
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int base = 1e9+3;
long long n,m,K;
char a[505][505];
long long Hash[505][505][32],power[32];
map<long long,long long> cnt;
long long dx[] = {0,-1,0,1,-1,-1,1,1};
long long dy[] = {-1,0,1,0,-1,1,-1,1};
long long cal(long long i,long long j,long long dir) {
    long long res = 0;
    for (int p = 0; p < 31; p++) {
        if ((K >> p)&1) {
            res = (res*power[p]+Hash[i][j][p])%mod;
            i = (i+(1ll << p)*dx[dir]%m+m)%m;
            j = (j+(1ll << p)*dy[dir]%n+n)%n;
        }
    }
    return res;
}
void solve() {
    cin >> m >> n >> K;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    power[0] = base;
    for (int i = 1; i < 31; i++) power[i] = (power[i-1]*power[i-1])%mod;
    for (int dir = 0; dir < 8; dir++) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Hash[i][j][0] = a[i][j];
            }
        }
        for (int p = 1; p < 31; p++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    long long u = (i+(1ll << (p-1))*dx[dir]%m+m)%m;
                    long long v = (j+(1ll << (p-1))*dy[dir]%n+n)%n;
                    Hash[i][j][p] = (Hash[i][j][p-1]*power[p-1]+Hash[u][v][p-1])%mod;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cnt[cal(i,j,dir)]++;
            }
        }
    }
    long long y = 1ll*(n*m*8)*(n*m*8);
    long long x = 0;
    for (auto p:cnt) {
        x += 1ll*p.second*p.second;
    }
    long long d = __gcd(x,y);
    x /= d;
    y /= d;
    cout << x << "/" << y;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...