#define _GLIBCXX_FILESYSTEM
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define int long long
using namespace std;
int n,m,k;
int b=31;
int mod=(1ll<<61)-1;
map<int,int> mp;
void roh(string x)
{
int sz=min((int)x.size(),k);
vector<__int128> h(x.size());
vector<__int128> p(x.size());
p[0]=1;
h[0]=x[0];
for(int i=1; i<x.size(); i++)
{
p[i]=(p[i-1]*b)%mod;
h[i]=((h[i-1]*b)%mod+x[i] )%mod;
}
int l1,l2,r1,r2;
for(int i=0; i<x.size(); i++)
{
l1=l2=r1=r2=-1;
l1=i;
r1 =min((int)x.size()-1,i+sz-1);
if(r1-l1+1 <sz)
{
l2=0;
int need=sz-(r1-l1+1);
r2=need-1;
}
int value=0;
if(l2==-1)
{
if(l1==0)
value=h[r1];
else
value=((h[r1]-(h[l1-1]*p[r1-l1+1]%mod))+mod)%mod;
}
else
{
__int128 value1=h[r2];
__int128 value2=(h[r1]-((h[l1-1]*p[r1-l1+1])%mod)+mod)%mod;
value=(value1+ (value2*p[r2+1])%mod)%mod;
}
mp[(int)value]++;
}
}
signed main()
{
IOS
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
b=uniform_int_distribution<int>(0,1e9)(rnd);
cin>>n>>m>>k;
vector<vector<char>> grid(n,vector<char>(m));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>grid[i][j];
}
}
for(int i=0; i<n; i++)
{
string x;
for(int j=0; j<m; j++)
{
x.push_back(grid[i][j]);
}
roh(x);
reverse(x.begin(),x.end());
roh(x);
}
for(int j=0; j<m; j++)
{
string x;
for(int i=0; i<n; i++)
{
x.push_back(grid[i][j]);
}
roh(x);
reverse(x.begin(),x.end());
roh(x);
}
vector<vector<int>> vis(n,vector<int>(m));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(!vis[i][j])
{
string x;
vis[i][j]=true;
x.push_back(grid[i][j]);
int ii=(i-1+n)%n;
int jj=(j-1+m)%m;
while(ii!=i || jj!=j)
{
vis[ii][jj]=true;
x.push_back(grid[ii][jj]);
ii=(ii-1+n)%n;
jj=(jj-1+m)%m;
}
roh(x);
// reverse(x.begin(),x.end());
// roh(x);
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
vis[i][j]=0;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(!vis[i][j])
{
string x;
vis[i][j]=true;
x.push_back(grid[i][j]);
int ii=(i+1+n)%n;
int jj=(j+1+m)%m;
while(ii!=i || jj!=j)
{
vis[ii][jj]=true;
x.push_back(grid[ii][jj]);
ii=(ii+1)%n;
jj=(jj+1)%m;
}
roh(x);
// reverse(x.begin(),x.end());
// roh(x);
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
vis[i][j]=0;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(!vis[i][j])
{
string x;
vis[i][j]=true;
x.push_back(grid[i][j]);
int ii=(i-1+n)%n;
int jj=(j+1+m)%m;
while(ii!=i || jj!=j)
{
vis[ii][jj]=true;
x.push_back(grid[ii][jj]);
ii=(ii-1+n)%n;
jj=(jj+1)%m;
}
roh(x);
//reverse(x.begin(),x.end());
//roh(x);
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
vis[i][j]=0;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(!vis[i][j])
{
string x;
vis[i][j]=true;
x.push_back(grid[i][j]);
int ii=(i+1)%n;
int jj=(j-1+m)%m;
while(ii!=i || jj!=j)
{
vis[ii][jj]=true;
x.push_back(grid[ii][jj]);
ii=(ii+1)%n;
jj=(jj-1+m)%m;
}
roh(x);
//reverse(x.begin(),x.end());
//roh(x);
}
}
}
int num,den;
num=0;
den=n*m*8*n*m*8;
for(auto [a,b]:mp)
{
num+= (b*b);
}
int g=gcd(num,den);
cout<<(num/g)<<"/"<<(den/g);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |