#pragma GCC optimize(3)
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.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=1e6+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;
}
cc_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: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;
}
Compilation message
osmosmjerka.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
osmosmjerka.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
osmosmjerka.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
osmosmjerka.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
osmosmjerka.cpp:64:26: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
64 | auto&operator[](Key x){
| ^
osmosmjerka.cpp:64:26: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:64:26: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:64:26: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
72 | auto begin(){return aps.begin();}
| ^
osmosmjerka.cpp:72:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:72:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
73 | auto end(){return aps.end();}
| ^
osmosmjerka.cpp:73:14: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:73:14: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
75 | ull qpow(ull a,lint b){
| ^
osmosmjerka.cpp:75:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:75:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
85 | void initpw(int x){
| ^
osmosmjerka.cpp:85:18: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:85:18: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
90 | lint a,lint b,lint n,lint m,lint k){
| ^
osmosmjerka.cpp:90:39: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:90:39: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp: In function 'auto solve(std::vector<std::__cxx11::basic_string<char> >&, lint, lint, lint, lint, lint)':
osmosmjerka.cpp:95:9: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
95 | [&](){
| ^
osmosmjerka.cpp:95:9: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:95:9: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:95:9: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp: At global scope:
osmosmjerka.cpp:126:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
126 | int main(){
| ^
osmosmjerka.cpp:126:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:126:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
osmosmjerka.cpp:126:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
13 ms |
23740 KB |
Output is correct |
| 4 |
Correct |
15 ms |
23960 KB |
Output is correct |
| 5 |
Correct |
28 ms |
24236 KB |
Output is correct |
| 6 |
Correct |
79 ms |
29092 KB |
Output is correct |
| 7 |
Correct |
1059 ms |
63100 KB |
Output is correct |
| 8 |
Execution timed out |
4074 ms |
131840 KB |
Time limit exceeded |
