Submission #1322131

#TimeUsernameProblemLanguageResultExecution timeMemory
1322131ssseulOsmosmjerka (COCI17_osmosmjerka)C++20
160 / 160
773 ms112744 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pii pair<int,int>
#define el '\n'

typedef vector<vector<int>> matrix;


const int maxN = 505;
const int base = 311;
const int MOD = 1000000003;
const int base2 = 307;
const int MOD2 = 1000000007;
const int INF = 1e15;
const int NEG_INF = -1e15;
const int LOG = 20;

int n, q, m, a, b, t, k, C;
string s;
// int dist[maxN];
int A[maxN], B[maxN];
int match[maxN], parent[maxN], block[maxN];
bool visited[maxN];
int fac[maxN];
int cntT[30], cntS[30];

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int H[205][205], H2[maxN], R[maxN], power[maxN], power2[maxN], pb1[LOG], pb2[LOG];
string SS[maxN];
string S, T;

int getHash( int i, int j, const int H[]){
    if(i > j) return 0;
    return (H[j] - H[i-1] * power[j-i+1] + MOD*MOD) % MOD;
}

int getHash2( int i, int j){
    return (H2[j] - H2[i-1] * power2[j-i+1] + MOD2*MOD2) % MOD2;
}

// int getHashT( int i, int j ){
//     return (R[j] - R[i-1] * power[j-i+1] + MOD*MOD) % MOD;
// }

int add(int a, int b, int mod) {
    return (a + b) % mod;
}
int mul(int a, int b, int mod) {
    return (a * b) % mod;
}

pii dp[LOG][maxN][maxN];

vector<pii> final_hashes;

void solve_dir(int dir){
    int dr = dx[dir];
    int dc = dy[dir];

    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            dp[0][i][j] = {SS[i][j], SS[i][j]};
        }
    }

    int cur_len = 1; // 2^0
    for (int p = 1; p < LOG; p++) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                
                int step_r = (dr * (cur_len % m)) % m;
                int ni = ((i - 1 + step_r) % m + m) % m + 1;

                int step_c = (dc * (cur_len % n)) % n;
                int nj = ((j - 1 + step_c) % n + n) % n + 1;

                int h1 = add(mul(dp[p-1][i][j].fi, pb1[p-1], MOD), dp[p-1][ni][nj].fi, MOD);
                int h2 = add(mul(dp[p-1][i][j].se, pb2[p-1], MOD2), dp[p-1][ni][nj].se, MOD2);

                dp[p][i][j] = {h1, h2};
            }
        }
        cur_len *= 2;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int h1 = 0, h2 = 0;
            int ci = i, cj = j;

            for (int p = LOG - 1; p >= 0; p--) {
                if ((k >> p) & 1) {
                    
                    h1 = add(mul(h1, pb1[p], MOD), dp[p][ci][cj].fi, MOD);
                    h2 = add(mul(h2, pb2[p], MOD2), dp[p][ci][cj].se, MOD2);

                    int step = (1LL << p);
                    
                    int step_r = (dr * (step % m)) % m;
                    ci = ((ci - 1 + step_r) % m + m) % m + 1;

                    int step_c = (dc * (step % n)) % n;
                    cj = ((cj - 1 + step_c) % n + n) % n + 1;
                }
            }
            final_hashes.push_back({h1, h2});
        }
    }
}


void run_test() {

    cin >> m >> n >> k;

    // n = S.length();
    // m = T.length();
    
    // S = '_' + S;
    // T = '_' + T;

    // int HashT = 0;

    // for( int i = 1; i <= n; i++ ){
    //     H[i] = (H[i-1] * base + S[i] - 'a' + 1) % MOD;
    // }

    // for( int i = 1; i <= m; i++ ){
    //     HashT = (HashT * base + T[i] - 'a' + 1) % MOD;
    // }

    for(int i = 1; i <= m; i++){
        cin >> SS[i];
        SS[i] = '_' + SS[i];
    }

    pb1[0] = base;
    pb2[0] = base2;
    for (int p = 1; p < LOG; p++) {
        pb1[p] = mul(pb1[p-1], pb1[p-1], MOD);
        pb2[p] = mul(pb2[p-1], pb2[p-1], MOD2);
    }

    for(int i = 0; i < 8; i++){
        solve_dir(i);
    }

    sort(all(final_hashes));

    int numerator = 0;
    int cur_cnt = 0;
    for (int i = 0; i < final_hashes.size(); i++) {
        cur_cnt++;
        if (i == final_hashes.size() - 1 || final_hashes[i] != final_hashes[i+1]) {
            numerator += cur_cnt * cur_cnt;
            cur_cnt = 0;
        }
    }

    int total_choices = m * n * 8;
    int denominator = total_choices * total_choices;

    int common = __gcd(numerator, denominator);
    cout << numerator / common << "/" << denominator / common << el;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("lightsout.in", "r", stdin); 
    // freopen("lightsout.out", "w", stdout);
    int test = 1;
    // cin >> test;
    while (test-- > 0)
    {
        run_test();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...