제출 #1357319

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

long long n,m,K;
char a[505][505];
const int base = 1e9+3;
const int mod = 1e9+7;
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]);
            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]);
    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 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]);
                }
            }
        }
        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();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…