// Osmosmjerka.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int A = 9973;
int B = 1e9 + 7;
int gcd(long long int a, long long int b) {
if (a == 0)
return b;
if (b == 0)
return a;
if (a == b)
return a;
if (a > b)
return gcd(a - b, b);
return gcd(a, b - a);
}
int main()
{
int M, N, K;
cin >> M >> N >> K;
long long int tmphash = 0;
long long int numerator = 0;
long long int denominator = 64 * M * M * N * N;
int period = M*N / gcd(M, N);
string tmp;
vector<vector<char>> input;
unordered_map<long long int, int> hashes;
for (int i = 0; i < M; i++) {
cin >> tmp;
input.push_back({});
for (char c : tmp) {
input[i].push_back(c);
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
tmphash += input[(i+x)%M][j];
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
if ((i - x) % M >= 0) {
tmphash += input[(i - x) % M][j];
}
else {
tmphash += input[(i - x) % M + M][j];
}
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
tmphash += input[i][(j+x) % N];
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
if ((j - x) % N >= 0) {
tmphash += input[i][(j-x) % N];
}
else {
tmphash += input[i][(j-x) % N + N];
}
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
tmphash += input[(i + x) % M][(j+x)%N];
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
if ((j - x) % N >= 0) {
tmphash += input[(i + x) % M][(j - x) % N];
}
else {
tmphash += input[(i + x) % M][(j - x) % N + N];
}
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
if ((i - x) % M >= 0) {
tmphash += input[(i - x) % M][(j + x) % N];
}
else {
tmphash += input[(i - x) % M + M][(j + x) % N];
}
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
tmphash = 0;
for (int x = 0; x < period; x++) {
tmphash *= A;
tmphash %= B;
if ((i - x) % M >= 0) {
if ((j - x) % N >= 0) {
tmphash += input[(i - x) % M][(j - x) % N];
}
else {
tmphash += input[(i - x) % M][(j - x) % N + N];
}
}
else {
if ((j - x) % N >= 0) {
tmphash += input[(i - x) % M + M][(j - x) % N];
}
else {
tmphash += input[(i - x) % M + M][(j - x) % N + N];
}
}
tmphash %= B;
}
if (tmphash < 0) {
tmphash += B;
}
if (hashes[tmphash]) {
hashes[tmphash] ++;
}
else {
hashes[tmphash] = 1;
}
}
}
for (auto i : hashes) {
numerator += i.second * i.second;
}
cout << numerator / gcd(numerator, denominator) << "/" << denominator / gcd(numerator, denominator);
}
// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu
// Tips for Getting Started:
// 1. Use the Solution Explorer window to add/manage files
// 2. Use the Team Explorer window to connect to source control
// 3. Use the Output window to see build output and other messages
// 4. Use the Error List window to view errors
// 5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
// 6. In the future, to open this project again, go to File > Open > Project and select the .sln file
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
12 ms |
320 KB |
Output is correct |
| 6 |
Execution timed out |
4056 ms |
1132 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4062 ms |
652 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4053 ms |
5184 KB |
Time limit exceeded |
