Submission #477705

#TimeUsernameProblemLanguageResultExecution timeMemory
477705MohammadAghilOsmosmjerka (COCI17_osmosmjerka)C++14
140 / 160
2160 ms78048 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pp; #define rep(i,l,r) for(int i = (l); i < r; i++) #define per(i,r,l) for(int i = (r); i >= l; i--) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() #define pb push_back #define ff first #define ss second // #include <ext/pb_ds/assoc_container.hpp> // using namespace __gnu_pbds; // template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll mod = 1e9 + 9, maxn = 5e2 + 5, inf = 1e9 + 5, p = 9973, lg = 31; ll jmp[maxn][maxn][lg]; int n, m, k; ll pw[lg]; vector<ll> st; ll add(int a, int b, int c, int md){ return (a + ((1LL << b)%md)*c + md)%md; } void calc(int x, int y){ rep(k,1,lg){ rep(i,0,n){ rep(j,0,m){ jmp[i][j][k] = (jmp[i][j][k-1]*pw[k-1]%mod + jmp[add(i, k-1, x, n)][add(j, k-1, y, m)][k-1])%mod; } } } rep(i,0,n){ rep(j,0,m){ ll res = 0; pp cr = {i, j}; rep(b,0,lg){ if(k&(1LL << b)){ res = (res*pw[b]%mod + jmp[cr.ff][cr.ss][b])%mod; cr.ff = add(cr.ff, b, x, n); cr.ss = add(cr.ss, b, y, m); } } st.pb(res); } } } int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n >> m >> k; rep(i,0,n){ rep(j,0,m){ char c; cin >> c; jmp[i][j][0] = int(c); } } pw[0] = p; rep(i,1,lg){ pw[i] = 1LL*pw[i-1]*pw[i-1]%mod; } rep(i,-1,2){ rep(j,-1,2){ if(i == 0 && j == 0) continue; calc(i, j); } } sort(all(st)); ll lst = -1, cnt = 0; ll t = 0, b = 64LL*n*n*m*m; rep(i,0,sz(st)){ if(lst != st[i]){ t += 1LL*cnt*cnt; cnt = 0; } lst = st[i]; cnt++; } t += cnt*cnt; ll g = __gcd(t, b); cout << t/g << '/' << b/g; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...