Submission #1018125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018125		DanielPr8	Osmosmjerka (COCI17_osmosmjerka)	C++17	120 / 160	382 ms	262144 KiB

osmosmjerka

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
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){
            cin >> tab[i][j];
        }
    }
    ll mod1 = 1e9+7, a1 = rand();
    ll mod2 = 1e9+9, a2 = rand()+3;
    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;
}

• Subtask 1: 120 / 160