#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// Miscellanous
#define ll long long
#define ull unsigned long long
#define si(x) scanf("%d",&x)
#define si2(x,y) scanf("%d %d",&x,&y)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)
#define pi(x) printf("%d\n",x)
#define pi2(x,y) printf("%d %d\n",x,y)
#define pl(x) printf("%lld\n",x)
#define pl2(x,y) printf("%lld %lld\n",x,y)
#define ps(s) cout << s << endl
#define py printf("YES\n")
#define pn printf("NO\n")
#define pnl printf("\n")
#define pb push_back
#define ff first
#define ss second
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define sortv(v) sort(all(v))
#define clr(x) memset(x, 0, sizeof(x))
// Loops
#define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
#define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
#define forc(c,s,e) for (char (c)=(s);(c)<=(e);++(c))
#define rep(i,n) loop(i,0,n)
#define repn(i,n) loope(i,1,n)
// Constants
#define PI 3.1415926535897932384626
// Containers
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<string,string> pss;
typedef map<int, int> mii;
// Input Output
#define takei(a) int a; si(a)
#define takei2(a,b) int a,b; si2(a,b)
#define takel(a) ll a; sl(a)
#define takel2(a,b) ll a,b; sl2(a,b)
#define takearri0(n,a) vi a(n); rep(i,n) si(a[i])
#define takearri1(n,a) vi a(n+1); a[0] = 0; repn(i,n) si(a[i])
#define takearrl0(n,a) vl a(n); rep(i,n) sl(a[i])
#define takearrl1(n,a) vl a(n+1); a[0] = 0ll; repn(i,n) sl(a[i])
// Debug
void _print(int t) {cerr << t;}
void _print(ll t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(unordered_set <T> v);
template <class T> void _print(unordered_multiset <T> v);
template <class T> void _print(set <T> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(unordered_map <T, V> v);
template <class T, class V> void _print(unordered_multimap <T, V> v);
template <class T, class V> void _print(map <T, V> v);
template <class T, class V> void _print(multimap <T, V> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(unordered_multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(unordered_multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(multimap <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
#ifndef ONLINE_JUDGE
#define deb(x) cerr << #x << " = "; _print(x); cerr << endl;
#else
#define deb(x)
#endif
inline string inttostr(ll a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline ll strtoint(string a){
char x[100]; ll res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string uppercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = sz(s);
rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937_64 rng(seq);
const uint64_t MOD = (1ll << 61) - 1;
const ll BASE = uniform_int_distribution<ll>(2,MOD-1)(rng);
static inline ll add(ll x, ll y) {x+=y; return x >= MOD ? x-MOD : x;}
static inline ll sub(ll x, ll y) {x-=y; return x < 0 ? x+MOD : x;}
static inline uint64_t mul(uint64_t x,uint64_t y)
{
__int128_t z = (__int128_t)x*y;
z = (z&MOD) + (z>>61);
return z >= MOD ? z-MOD : z;
}
unordered_map<ll, int> mp;
int n,m,k;
// SPARSE TABLE
const int MAXN = 500;
const int LOGK = 30;
ll hash_[MAXN][MAXN][LOGK];
ll bpow[LOGK]; // bpow[i] = BASE ^ (2^i)
char v[MAXN][MAXN];
static inline int ADD(int i, int dx , int n)
{
i += dx;
if(i < 0) i += n;
else if(i >= n) i -= n;
return i;
}
static inline ll concat(ll l, ll r, ll factor) {return add(l, mul(r, factor));}
void init()
{
bpow[0] = BASE;
repn(x,LOGK-1) bpow[x] = mul(bpow[x-1] , bpow[x-1]);
}
void solve(int dx, int dy)
{
// BASE CASE
rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
// BUILDING TABLE
repn(k,LOGK-1)
{
rep(i,n) rep(j,m)
{
ll pi = i + dx*(1<<(k-1));
ll pj = j + dy*(1<<(k-1));
if(pi < 0) pi += 1ll*n*1e9;
if(pj < 0) pj += 1ll*m*1e9;
pi %= n; pj %= m;
hash_[i][j][k] = concat(hash_[i][j][k-1] , hash_[pi][pj][k-1] , bpow[k-1]);
}
}
rep(i,n) rep(j,m)
{
ll hash = 0, factor = 1;
ll tmp_k = k, pi = i, pj = j;
for (int x = LOGK - 1; x >= 0; x--)
{
if((1<<x) <= tmp_k)
{
hash = concat(hash , hash_[pi][pj][x] , factor);
tmp_k -= (1<<x);
factor = mul(factor , bpow[x]);
pi += (1<<x)*dx , pj += (1<<x)*dy;
if(pi < 0) pi += 1ll*n*1e9;
if(pj < 0) pj += 1ll*m*1e9;
pi %= n; pj %= m;
}
}
mp[hash]++;
}
}
int main()
{
init();
scanf("%d%d%d", &n, &m, &k);
rep(i,n)
{
string s; cin >> s;
rep(j,m) v[i][j] = s[j];
}
loope(i,-1,1) loope(j,-1,1)
{
if(!i and !j) continue;
solve(i,j);
}
ll deno = 1ll * n*n*m*m*8*8;
ll num = 0;
for(auto &pr : mp) num += 1ll * pr.ss * pr.ss;
ll g = __gcd(num , deno);
num /= g, deno /= g;
printf("%lld/%lld\n", num, deno);
return 0;
}
// ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Compilation message
osmosmjerka.cpp: In function 'std::string uppercase(std::string)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:117:3: note: in expansion of macro 'rep'
117 | rep(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
| ^~~
osmosmjerka.cpp: In function 'std::string lowercase(std::string)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:123:3: note: in expansion of macro 'rep'
123 | rep(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
| ^~~
osmosmjerka.cpp: In function 'long long int add(long long int, long long int)':
osmosmjerka.cpp:139:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
139 | static inline ll add(ll x, ll y) {x+=y; return x >= MOD ? x-MOD : x;}
| ~~^~~~~~
osmosmjerka.cpp: In function 'void init()':
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
osmosmjerka.cpp:35:19: note: in expansion of macro 'loope'
35 | #define repn(i,n) loope(i,1,n)
| ^~~~~
osmosmjerka.cpp:172:3: note: in expansion of macro 'repn'
172 | repn(x,LOGK-1) bpow[x] = mul(bpow[x-1] , bpow[x-1]);
| ^~~~
osmosmjerka.cpp: In function 'void solve(int, int)':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:178:5: note: in expansion of macro 'rep'
178 | rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
| ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:178:14: note: in expansion of macro 'rep'
178 | rep(i,n) rep(j,m) hash_[i][j][0] = v[i][j];
| ^~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
osmosmjerka.cpp:35:19: note: in expansion of macro 'loope'
35 | #define repn(i,n) loope(i,1,n)
| ^~~~~
osmosmjerka.cpp:181:5: note: in expansion of macro 'repn'
181 | repn(k,LOGK-1)
| ^~~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:183:9: note: in expansion of macro 'rep'
183 | rep(i,n) rep(j,m)
| ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:183:18: note: in expansion of macro 'rep'
183 | rep(i,n) rep(j,m)
| ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:195:5: note: in expansion of macro 'rep'
195 | rep(i,n) rep(j,m)
| ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:195:14: note: in expansion of macro 'rep'
195 | rep(i,n) rep(j,m)
| ^~~
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:222:3: note: in expansion of macro 'rep'
222 | rep(i,n)
| ^~~
osmosmjerka.cpp:31:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
31 | #define loop(i,s,e) for (int (i)=(s);(i)<(e);++(i))
| ^
osmosmjerka.cpp:34:18: note: in expansion of macro 'loop'
34 | #define rep(i,n) loop(i,0,n)
| ^~~~
osmosmjerka.cpp:225:5: note: in expansion of macro 'rep'
225 | rep(j,m) v[i][j] = s[j];
| ^~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
osmosmjerka.cpp:228:3: note: in expansion of macro 'loope'
228 | loope(i,-1,1) loope(j,-1,1)
| ^~~~~
osmosmjerka.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
32 | #define loope(i,s,e) for (int (i)=(s);(i)<=(e);++(i))
| ^
osmosmjerka.cpp:228:17: note: in expansion of macro 'loope'
228 | loope(i,-1,1) loope(j,-1,1)
| ^~~~~
osmosmjerka.cpp:220:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
220 | scanf("%d%d%d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
8 ms |
6696 KB |
Output is correct |
| 6 |
Correct |
48 ms |
15020 KB |
Output is correct |
| 7 |
Correct |
559 ms |
37452 KB |
Output is correct |
| 8 |
Correct |
2776 ms |
81464 KB |
Output is correct |
