Submission #370142

# Submission time Handle Problem Language Result Execution time Memory
370142 2021-02-23T11:43:46 Z Atill83 Osmosmjerka (COCI17_osmosmjerka) C++14
140 / 160
3303 ms 55916 KB
```#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 5e2+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, m, k;
string s[MAXN];
int g[MAXN][MAXN];
const int base = 35;
map<int, int> mp;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int L = 30;
int par[MAXN][MAXN][L];
int basep[L];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);

#ifdef Local
#endif

cin>>n>>m>>k;

for(int i = 0; i < n; i++){
cin>>s[i];
for(int j = 0; j < m; j++)
g[i][j] = s[i][j] - 'a' + 1;
}
basep[0] = base;
for(int i = 1; i < L; i++){
basep[i] = 1LL * basep[i - 1] * basep[i - 1] % mod;
}

for(int i = 0; i < 8; i++){
dx[i] = (dx[i] + n) % n;
dy[i] = (dy[i] + m) % m;
}

for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
par[i][j][0] = g[i][j];
}
}

for(int s = 0; s < 8; s++){

for(int p = 1; p < L; p++){
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int nx = (i + 1LL * dx[s] * (1<<(p - 1)) % n) % n,
ny = (j + 1LL * dy[s] * (1<<(p - 1)) % m) % m;
par[i][j][p] = (par[i][j][p - 1] + 1LL * basep[p - 1] * par[nx][ny][p - 1] % mod) % mod;
}
}
}

for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int hsh = 0;
int cur = k;
int bas = 1;
int nx = i, ny = j;

for(int l = L - 1; l >= 0; l--){
if((1<<l) <= cur){
hsh = (hsh + 1LL * bas * par[nx][ny][l] % mod) % mod;
nx = (nx + 1LL * dx[s] * (1<<l) % n) % n,
ny = (ny + 1LL * dy[s] * (1<<l) % m) % m;
bas = 1LL * bas * basep[l] % mod;
cur -= (1<<l);
}
}
mp[hsh]++;
}
}
}

ll toplam = 8LL * n * m;
toplam = toplam * toplam;

ll ist = 0;

for(auto u: mp){
ist += 1LL * u.ss * u.ss;
}

ll gc = __gcd(ist, toplam);

ist /= gc;
toplam /= gc;

cout<<ist<<"/"<<toplam<<endl;

#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}```