#include<bits/stdc++.h>
#include<bits/extc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
using ull=unsigned long long;
using VU=vector<ull>;
const ull hashc=251;
template<typename Key,
typename T,class func=hash<Key>>
class cc_hash_table{
private:
static const int mem=5e6+7;
array<list<pair<Key,T>>,mem> ht;
func f;
list<T> aps;
public:
auto&operator[](Key x){
const int p=f(x)%mem;
for(auto&[k,t]:ht[p]) if(k==x)
return t;
aps.push_back(x);
ht[p].push_back({x,0});
return ht[p].back().second;
}
auto begin(){return aps.begin();}
auto end(){return aps.end();}
};
ull qpow(ull a,lint b){
ull res=1;
while(b){
if(b&1) res*=a;
a*=a;b>>=1;
}
return res;
}
__gnu_pbds::gp_hash_table<ull,ull> cnx;
VU pw;
void initpw(int x){
pw.clear();pw.resize(x);
cir(i,0,x) pw[i]=qpow(hashc,(1<<i));
}
auto solve(vector<string>&s,
lint a,lint b,lint n,lint m,lint k){
const int __lg2=log2(k)+2;
initpw(__lg2);
vector<vector<VU>> g(
n,vector<VU>(m,VU(__lg2)));
[&](){
cir(i,0,n) cir(j,0,m)
g[i][j][0]=s[i][j];
}();
cir(x,1,__lg2){
cir(i,0,n) cir(j,0,m){
const int ni=((i+a*(
((1<<x)>>1)))%n+n)%n;
const int nj=((j+b*(
((1<<x)>>1)))%m+m)%m;
g[i][j][x]=g[i][j][x-1]*
(x?pw[x-1]:(ull)(0))
+g[ni][nj][x-1];
}
}
cir(i,0,n) cir(j,0,m){
ull alw=0;
int ix=i,jx=j,w=k;
cir(x,0,__lg2){
if(k&(1<<x)){
alw+=g[ix][jx][x]*
qpow(hashc,w-=(1<<x));
ix=((ix+a*((
(1<<x)>>1)+1))%n+n)%n;
jx=((jx+b*((
(1<<x)>>1)+1))%m+m)%m;
}
}
++cnx[alw];
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,k;cin>>n>>m>>k;
vector<string> s(n);
for(auto&i:s) cin>>i;
cir(a,-1,2) cir(b,-1,2) if(a||b){
solve(s,a,b,n,m,k);
}
lint ans=0;
for(auto&[x,y]:cnx)
ans+=qpow(cnx[x],2);
const lint all=qpow(n*m*8,2);
const lint g=__gcd(ans,all);
cout<<ans/g<<'/'<<all/g<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1028 KB |
Output is correct |
| 6 |
Correct |
45 ms |
6812 KB |
Output is correct |
| 7 |
Correct |
878 ms |
52864 KB |
Output is correct |
| 8 |
Correct |
3878 ms |
106192 KB |
Output is correct |
