#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int M=1e9+9;
const unsigned ll SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
uniform_int_distribution<int> BDIST(0.1*M, 0.9*M);
ar<int, 2> B={BDIST(rng), BDIST(rng)};
ar<int, 2> operator+(ar<int, 2> a, ar<int, 2> b) {
ar<int, 2> c;
for (int i : {0, 1})
if ((c[i]=a[i]+b[i])>=M)
c[i]-=M;
return c;
}
ar<int, 2> operator-(ar<int, 2> a, ar<int, 2> b) {
ar<int, 2> c;
for (int i : {0, 1})
if ((c[i]=a[i]-b[i])<0)
c[i]+=M;
return c;
}
ar<int, 2> operator*(ar<int, 2> a, ar<int, 2> b) {
return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
}
ar<int, 2> mk(char c) {
return {c, c};
}
ostream& operator<<(ostream& out, ar<int, 2> a) {
return out << "[" << a[0] << ", " << a[1] << "]";
}
const int mxN=500;
int n, m, k;
string g[mxN], ng[mxN];
bool vis[mxN][mxN];
ar<int, 2> hsh[mxN*mxN+1], p[mxN*mxN+1];
map<ar<int, 2>, int> mp;
void rot() {
for (int i=0; i<m; ++i)
ng[i].resize(n);
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
ng[j][n-i-1]=g[i][j];
swap(n, m);
for (int i=0; i<n; ++i)
g[i]=ng[i];
}
void solve(string s) {
for (int i=0; i<s.size(); ++i)
hsh[i+1]=hsh[i]*B+mk(s[i]);
int need=(k-s.size()+1)/s.size();
int rem=k-need*s.size();
assert(rem>=s.size()-1);
ar<int, 2> hp=hsh[s.size()], bp=p[s.size()];
ar<int, 2> hr={}, br={1, 1};
while(need) {
if (need&1) {
hr=hr*bp+hp;
br=br*bp;
}
hp=hp*bp+hp;
bp=bp*bp;
need/=2;
}
//cout << s << endl;
for (int i=0; i<s.size(); ++i) {
ar<int, 2> cur;
int lft;
if (!i)
cur=hr, lft=rem;
else {
cur=(hsh[s.size()]-hsh[i]*p[s.size()-i])*br+hr;
lft=rem-(s.size()-i);
}
//cout << cur << endl;
int pos=0;
while(lft) {
if (s.size()-pos>=lft) {
cur=cur*p[lft]+(hsh[pos+lft]-hsh[pos]*p[lft]);
break;
} else {
cur=cur*p[s.size()-pos]+(hsh[s.size()]-hsh[pos]*p[s.size()-pos]);
lft-=s.size()-pos;
}
}
++mp[cur];
//cout << cur << endl;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for (int i=0; i<n; ++i)
cin >> g[i];
p[0]={1, 1};
for (int i=1; i<=n*m; ++i)
p[i]=p[i-1]*B;
for (int r=0; r<4; ++r) {
for (int i=0; i<n; ++i)
solve(g[i]);
memset(vis, 0, sizeof(vis));
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (!vis[i][j]) {
string s;
int a=i, b=j;
while(!vis[a][b]) {
vis[a][b]=1;
s+=g[a][b];
a=(a+1)%n;
b=(b+1)%m;
}
solve(s);
}
rot();
}
ll ans=0;
for (auto x : mp)
ans+=(ll)x.second*x.second;
ll b=(8ll*n*m)*(8*n*m);
ll g=__gcd(ans, b);
cout << ans/g << "/" << b/g;
return 0;
}
Compilation message
osmosmjerka.cpp: In function 'std::array<int, 2> operator*(std::array<int, 2>, std::array<int, 2>)':
osmosmjerka.cpp:30:23: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](0)) * ((long long int)b.std::array<int, 2>::operator[](0))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
30 | return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
| ~~~~~~~~~~~~~^~
osmosmjerka.cpp:30:40: warning: narrowing conversion of '((((long long int)a.std::array<int, 2>::operator[](1)) * ((long long int)b.std::array<int, 2>::operator[](1))) % ((long long int)((int)M)))' from 'long long int' to 'int' [-Wnarrowing]
30 | return {(ll)a[0]*b[0]%M, (ll)a[1]*b[1]%M};
| ~~~~~~~~~~~~~^~
osmosmjerka.cpp: In function 'void solve(std::string)':
osmosmjerka.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i=0; i<s.size(); ++i)
| ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from osmosmjerka.cpp:1:
osmosmjerka.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | assert(rem>=s.size()-1);
| ~~~^~~~~~~~~~~~
osmosmjerka.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i=0; i<s.size(); ++i) {
| ~^~~~~~~~~
osmosmjerka.cpp:89:20: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if (s.size()-pos>=lft) {
| ~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
592 KB |
Output is correct |
| 3 |
Correct |
1 ms |
592 KB |
Output is correct |
| 4 |
Correct |
1 ms |
592 KB |
Output is correct |
| 5 |
Correct |
3 ms |
720 KB |
Output is correct |
| 6 |
Correct |
23 ms |
3444 KB |
Output is correct |
| 7 |
Correct |
306 ms |
20900 KB |
Output is correct |
| 8 |
Correct |
1022 ms |
36256 KB |
Output is correct |
