Submission #834041

#	Time	Username	Problem	Language	Result	Execution time	Memory
834041		vjudge1	Osmosmjerka (COCI17_osmosmjerka)	C++17	160 / 160	3741 ms	227464 KiB

osmosmjerka

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
using ull=unsigned long long;
using VU=vector<ull>;
const ull hashc=251;
template<typename Key,
    typename T,class func=hash<Key>>
class cc_hash_table{
private:
    static const int mem=5e6+7;
    array<list<pair<Key,T>>,mem> ht;
    func f;
    list<T> aps;
public:
    auto&operator[](Key x){
        const int p=f(x)%mem;
        for(auto&[k,t]:ht[p]) if(k==x)
            return t;
        aps.push_back(x);
        ht[p].push_back({x,0});
        return ht[p].back().second;
    }
    auto begin(){return aps.begin();}
    auto end(){return aps.end();}
};
ull qpow(ull a,lint b){
    ull res=1;
    while(b){
        if(b&1) res*=a;
        a*=a;b>>=1;
    }
    return res;
}
cc_hash_table<ull,ull> cnx;
VU pw;
void initpw(int x){
    pw.clear();pw.resize(x);
    cir(i,0,x) pw[i]=qpow(hashc,(1<<i));
}
auto solve(vector<string>&s,
    lint a,lint b,lint n,lint m,lint k){
    const int __lg2=log2(k)+2;
    initpw(__lg2);
    vector<vector<VU>> g(
        n,vector<VU>(m,VU(__lg2)));
    [&](){
        cir(i,0,n) cir(j,0,m)
            g[i][j][0]=s[i][j];
    }();
    cir(x,1,__lg2){
        cir(i,0,n) cir(j,0,m){
            const int ni=((i+a*(
                ((1<<x)>>1)))%n+n)%n;
            const int nj=((j+b*(
                ((1<<x)>>1)))%m+m)%m;
            g[i][j][x]=g[i][j][x-1]*
                (x?pw[x-1]:(ull)(0))
                +g[ni][nj][x-1];
        }
    }
    cir(i,0,n) cir(j,0,m){
        ull alw=0;
        int ix=i,jx=j,w=k;
        cir(x,0,__lg2){
            if(k&(1<<x)){
                alw+=g[ix][jx][x]*
                    qpow(hashc,w-=(1<<x));
                ix=((ix+a*((
                    (1<<x)>>1)+1))%n+n)%n;
                jx=((jx+b*((
                    (1<<x)>>1)+1))%m+m)%m;
            }
        }
        ++cnx[alw];
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    vector<string> s(n);
    for(auto&i:s) cin>>i;
    cir(a,-1,2) cir(b,-1,2) if(a||b){
        solve(s,a,b,n,m,k);
    }
    lint ans=0;
    for(auto&x:cnx)
        ans+=qpow(cnx[x],2);
    const lint all=qpow(n*m*8,2);
    const lint g=__gcd(ans,all);
    cout<<ans/g<<'/'<<all/g<<'\n';
    return 0;
}

• Subtask 1: 160 / 160