oj.uz

Submission #477705

# Submission time Handle Problem Language Result Execution time Memory
477705 2021-10-03T07:33:32 Z MohammadAghil Osmosmjerka (COCI17_osmosmjerka) C++14
140 / 160
 2160 ms 78048 KB 
#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;
}

Subtask #1
140.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 6 ms 988 KB Output is correct
6 Correct 34 ms 3284 KB Output is correct
7 Correct 457 ms 19892 KB Output is correct
8 Incorrect 2160 ms 78048 KB Output isn't correct