#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=3137;
int mod=(1ll<<61)-1;
map<int,int> mp;
vector<__int128> p(502*530);
int pows(__int128 x,__int128 y)
{
__int128 ans=1;
while(y)
{
if(y%2)
ans=(ans*x)%mod;
y/=2;
x=(x*x)%mod;
}
return ans;
}
int hash_len(int start,vector<__int128> &h,int len)
{
int sz=h.size();
int l1,l2,r1,r2;
l1=l2=r1=r2=-1;
l1=start;
r1 =min(sz-1,start+len-1);
if(r1-l1+1 <len)
{
l2=0;
int need=len-(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);
if(value<0)value+=mod;
}
else
{
int value1=h[r1]-((h[l1-1]*p[r1-l1+1])%mod);
int value2=h[r2];
if(value1<0)value1+=mod;
value=((value1*p[r2+1]%mod)+value2)%mod;
}
return value;
}
void roh(string x)
{
int sz=min((int)x.size(),k);
vector<__int128> h(x.size());
h[0]=x[0];
for(int i=1; i<x.size(); i++) h[i]=(h[i-1]*b+x[i])%mod;
for(int i=0; i<x.size(); i++)
{
int value=hash_len(i,h,sz);
if(sz!=k)
{
int rem=k%sz;
int q=k/sz;
int r=p[sz];
__int128 num=1-(pows(r,q))+mod;
num=(value*num)%mod;
__int128 den=pows((1-r+mod),mod-2);
__int128 ans=(num*den)%mod;
value=ans;
if(rem!=0)
{
int hash_of_reminder=hash_len(i,h,rem);
value=((ans*p[rem])%mod+hash_of_reminder)%mod;
}
}
mp[value]++;
}
}
int vis[502][502];
signed main()
{
IOS
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];
p[0]=1;
for(int i=1; i<=n*m+10; i++)
p[i]=(p[i-1]*b)%mod;
int di[]= {-1,-1,0,1};
int dj[]= {1,-1,1,0};
for(int d=0; d<4; d++)
{
memset(vis,0,sizeof(vis));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(!vis[i][j])
{
vis[i][j]=true;
string x;
x.push_back(grid[i][j]);
int ii,jj;
ii=i;
jj=j;
while(true)
{
ii=(ii+di[d]+n)%n;
jj=(jj+dj[d]+m)%m;
if(ii==i && jj==j)break;
vis[ii][jj]=true;
x.push_back(grid[ii][jj]);
}
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... |