oj.uz

Submission #697144

# Submission time Handle Problem Language Result Execution time Memory
697144 2023-02-08T15:50:51 Z omikron123 Osmosmjerka (COCI17_osmosmjerka) C++14
100 / 160
 4000 ms 17752 KB 
// https://oj.uz/problem/view/COCI17_osmosmjerka

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

// 从任一点出发，最多LCM(M,N)个字符之后，就会出现重复的pattern，因此我们只要生成这个长度的hash，就可以找到所有唯一字符串了。
// 然后出现重复的概率，就是每个unique pattern概率的平方和。
// O(n^3)

int m,n,K;  // m,n <= 500, K <= 1e9
char s[505][505];   // M rows, N cols
int dir[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
int hsh[8][505][505];  // hash value patterns for 8 directions
int p[505];
map<int,int> cnts;    // hash -> count
const int A = 911382323, M = 972663749;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    scanf("%d %d %d", &m, &n, &K);
    for (int i = 0; i < m; i++)
        scanf("%s", s[i]);
    
    int lcm = m*n/gcd(m,n);
    if (K > lcm) K = lcm;
    int step = max(m,n);
    p[0] = 1;
    for (int i = 1; i <= step; i++)
        p[i] = (ll)p[i-1] * A % M;
        
    for (int di = 0; di < 8; di++)  // calc hash values for step-len strings from each pos
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                hsh[di][r][c] = s[r][c];
                int R = r, C = c;
                for (int i = 0; i < step; i++) {
                    hsh[di][r][c] = ((ll)hsh[di][r][c] * A + s[R][C]) % M;
                    R = (R + m + dir[di][0]) % m;
                    C = (C + n + dir[di][1]) % n;
                }
            }

    for (int di = 0; di < 8; di++)  // calc hashes for LCM-len strings from each pos
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                int hs = 0;
                int R = r, C = c;
                for (int i = 0; i < K/step; i++) {  // walk large steps
                    hs = ((ll)hs * p[step] + hsh[di][R][C]) % M;
                    R = (R + (ll)step*(m+dir[di][0])) % m;
                    C = (C + (ll)step*(n+dir[di][1])) % n;
                }
                for (int i = 0; i < K%step; i++) {  // remaining chars
                    hs = ((ll)hs * A + s[R][C]) % M;
                    R = (R + m + dir[di][0]) % m;
                    C = (C + n + dir[di][1]) % n;
                }
                cnts[hs]++;
            }
    ll total = m*n*8;
    total = total*total;
    ll squared = 0;
    for (auto e: cnts) {
        int v = e.second;
        squared += (ll)v*v;
    }
    ll g = gcd(total, squared);
    printf("%lld/%lld", squared/g, total/g);

    return 0;
}

Compilation message

osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d %d", &m, &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%s", s[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 6 ms 1108 KB Output is correct
6 Incorrect 131 ms 3952 KB Output isn't correct
7 Incorrect 2667 ms 17752 KB Output isn't correct
8 Execution timed out 4078 ms 4356 KB Time limit exceeded