#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using v3 = vector<vvl>;
using vvc = vector<vector<char>>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
vector<pair<ll,ll>> dir = {{1,0}, {1,1}, {0,1}, {-1, 1}, {-1,0}, {-1,-1}, {0, -1}, {1,-1}};
v3 lif(ll m, ll n, vvc ta, ll mod, ll a, ll k, ll l){
vector<v3> pr(l, v3(n, vvl(m, vll(8))));
vll pw = {a};
for(ll i = 0; i < l; ++i)pw.pb((pw.back()*pw.back())%mod);
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < m; ++j){
for(ll d = 0; d < 8; ++d){
pr[0][i][j][d] = ta[i][j]-'_';
}
}
}
for(ll f = 1; f < l; ++f){
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < m; ++j){
for(ll d = 0; d < 8; ++d){
pr[f][i][j][d] = pr[f-1][i][j][d]*pw[f-1] +
pr[f-1][ ((i+dir[d].f*(1<<(f-1)))%n+n)%n ][ ((j+dir[d].s*(1<<(f-1)))%m+m)%m ][d];
pr[f][i][j][d] %= mod;
}
}
}
}
vector<v3> ans;
ll las = 0;
for(ll f = 0; f < l; ++f){
if(!(k&(1<<f)))continue;
if(ans.empty()){las=f;ans.pb(pr[f]);continue;}
v3 cur(n, vvl(m, vll(8)));
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < m; ++j){
for(ll d = 0; d < 8; ++d){
cur[i][j][d] = ans.back()[i][j][d]*pw[f] +
pr[f][ ((i+dir[d].f*(1<<(las)))%n+n)%n ][ ((j+dir[d].s*(1<<(las)))%m+m)%m ][d];
cur[i][j][d] %= mod;
}
}
}
las=f;
ans.pb(cur);
}
return ans.back();
}
ll gcd(ll a, ll b){
return (b==0)?a:gcd(b, a%b);
}
int main(){
ll n, m, k;
cin >> n >> m >> k;
vvc tab(n, vector<char>(m));
ll l = 33-__builtin_clz(k);
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < m; ++j){
tab[i][j]='x';
}
}
mt19937 g1;
mt19937 g2;
ll mod1 = 1e9+7, a1 = g1()%mod1;
ll mod2 = 1e9+9, a2 = g2()%mod2;
v3 ans1 = lif(m, n, tab, mod1, a1, k, l);
v3 ans2 = lif(m, n, tab, mod2, a2, k, l);
map<pair<ll,ll>,ll> cnt;
for(ll i = 0; i < n; ++i){
for(ll j = 0; j < m; ++j){
for(ll d = 0; d < 8; ++d){
cnt[{ans1[i][j][d], ans2[i][j][d]}]++;
}
}
}
ll p=0, q=0;
for(auto [w,e]: cnt){
p += e*e;
q += e;
}
q *= q;
ll r = gcd(p,q);
cout << p/r << "/" << q/r;
}
Compilation message
osmosmjerka.cpp: In function 'int main()':
osmosmjerka.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto [w,e]: cnt){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
1372 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
5212 KB |
Output isn't correct |
| 6 |
Incorrect |
87 ms |
30032 KB |
Output isn't correct |
| 7 |
Runtime error |
380 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
153 ms |
262144 KB |
Execution killed with signal 9 |
