#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 503;
const int xx[8] = {0, 1, 0, -1, 1, -1, 1, -1};
const int yy[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const pair<int, int> M = m_p(891641833, 716000533);
const int P = 307;
bool prime(int x)
{
for (int i = 2; i * i <= x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
pair<int, int> sum(const pair<int, int>& a, const pair<int, int>& b)
{
return m_p((a.fi + b.fi) % M.fi, (a.se + b.se) % M.se);
}
pair<int, int> dif(const pair<int, int>& a, const pair<int, int>& b)
{
return m_p((a.fi - b.fi + M.fi) % M.fi, (a.se - b.se + M.se) % M.se);
}
pair<int, int> pro(const pair<int, int>& a, const pair<int, int>& b)
{
return m_p((a.fi * 1LL * b.fi) % M.fi, (a.se * 1LL * b.se) % M.se);
}
pair<int, int> ast[N];
void pre()
{
ast[0] = m_p(1, 1);
for (int i = 1; i < N; ++i)
ast[i] = pro(ast[i - 1], m_p(P, P));
}
pair<int, int> fast(pair<int, int> x, int n)
{
pair<int, int> ans = m_p(1, 1);
while (n)
{
if (n % 2 == 1)
ans = pro(ans, x);
x = pro(x, x);
n /= 2;
}
return ans;
}
ll gcd(ll x, ll y)
{
if (x == 0)
return y;
return gcd(y % x, x);
}
int n, m, k;
char a[N][N];
pair<int, int> h[30][N][N][8];
void solv()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; ++i)
{
scanf(" %s", a[i]);
}
for (int k = 0; k < 30; ++k)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
pair<int, int> astt = fast(m_p(P, P), (1 << (k - 1)));
for (int u = 0; u < 8; ++u)
{
if (k == 0)
{
h[k][i][j][u] = m_p(a[i][j], a[i][j]);
continue;
}
int i1 = (i + xx[u] * (1 << (k - 1))) % n;
int j1 = (j + yy[u] * (1 << (k - 1))) % m;
i1 = (i1 + n) % n;
j1 = (j1 + m) % m;
h[k][i][j][u] = sum(h[k - 1][i][j][u], pro(h[k - 1][i1][j1][u], astt));
}
}
}
}
ll ham = 0;
ll hay = (n * m * 8) * 1LL * (n * m * 8);
vector<pair<int, int> > v;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
for (int u = 0; u < 8; ++u)
{
int i1 = i;
int j1 = j;
pair<int, int> hh = m_p(0, 0);
int q = 0;
for (int b = 0; b < 30; ++b)
{
if ((k & (1 << b)))
{
hh = sum(hh, pro(fast(m_p(P, P), q), h[b][i][j][u]));
q += (1 << b);
i = (i + xx[u] * (1 << b)) % n;
j = (j + yy[u] * (1 << b)) % m;
i = (i + n) % n;
j = (j + m) % m;
}
}
v.push_back(hh);
i = i1;
j = j1;
}
}
}
sort(all(v));
int q = 1;
for (int i = 1; i < v.size(); ++i)
{
if (v[i] == v[i - 1])
++q;
else
{
ham += q * 1LL * q;
q = 1;
}
}
ham += q * 1LL * q;
ll g = gcd(ham, hay);
ham /= g;
hay /= g;
printf("%lld/%lld\n", ham, hay);
}
int main()
{
#ifdef SOMETHING
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif // SOMETHING
//ios_base::sync_with_stdio(false), cin.tie(0);
solv();
return 0;
}
//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}
Compilation message
osmosmjerka.cpp: In function 'void solv()':
osmosmjerka.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); ++i)
~~^~~~~~~~~~
osmosmjerka.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
osmosmjerka.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3840 KB |
Output is correct |
| 5 |
Correct |
31 ms |
8656 KB |
Output is correct |
| 6 |
Correct |
146 ms |
28680 KB |
Output is correct |
| 7 |
Correct |
1555 ms |
142180 KB |
Output is correct |
| 8 |
Runtime error |
1049 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
