oj.uz

Submission #370144

# Submission time Handle Problem Language Result Execution time Memory
370144 2021-02-23T11:44:30 Z Atill83 Osmosmjerka (COCI17_osmosmjerka) C++14
160 / 160
 3280 ms 56192 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 = 36;
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
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #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
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 49 ms 3948 KB Output is correct
7 Correct 867 ms 22892 KB Output is correct
8 Correct 3280 ms 56192 KB Output is correct