Submission #1220792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220792		super0200	Osmosmjerka (COCI17_osmosmjerka)	C++20	160 / 160	3013 ms	39540 KiB

osmosmjerka

#define _GLIBCXX_FILESYSTEM
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define int long long
using namespace std;



int n,m,k;
int b=3137;
int mod=(1ll<<61)-1;
map<int,int> mp;
vector<__int128> p(502*530);

int pows(__int128 x,__int128 y)
{
    __int128 ans=1;

    while(y)
    {
        if(y%2)
            ans=(ans*x)%mod;

        y/=2;
        x=(x*x)%mod;
    }

    return ans;
}

void roh(string x)
{

    int sz=min((int)x.size(),k);
    vector<__int128> h(x.size());
    h[0]=x[0];
    for(int i=1; i<x.size(); i++)
    {

        h[i]=(h[i-1]*b+x[i])%mod;
    }
    int l1,l2,r1,r2;
    for(int i=0; i<x.size(); i++)
    {
        l1=l2=r1=r2=-1;
        l1=i;
        r1 =min((int)x.size()-1,i+sz-1);
        if(r1-l1+1 <sz)
        {
            l2=0;
            int need=sz-(r1-l1+1);
            r2=need-1;
        }
        int value=0;

        if(l2==-1)
        {
            string ans;
            if(l1==0)
                value=h[r1];
            else
                value=(h[r1]-(h[l1-1]*p[r1-l1+1])%mod);

            if(value<0)value+=mod;
        }
        else
        {
            int value1=h[r2];
            int value2=h[r1]-((h[l1-1]*p[r1-l1+1])%mod);
            if(value2<0)value2+=mod;
            value=(value1+ (value2*p[r2+1])%mod)%mod;
        }

        if(sz!=k)
        {
            int rem=k%sz;
            int he=k/sz;
            int r=p[sz];

            __int128 num=1-(pows(r,he))+mod;
            num=(value*num)%mod;
            __int128 den=pows((1-r+mod),mod-2);
            __int128 ans=(num*den)%mod;

            if(rem==0)
            {
                mp[(int)ans]++;
                continue;
            }

            __int128 vv=0;

            int l1rem,l2rem,r1rem,r2rem;
            l1rem=l2rem=r1rem=r2rem=-1;

            l1rem=i;
            r1rem =min(sz-1,i+rem-1);

            if(r1rem-l1rem+1 <rem)
            {
                l2rem=0;
                int need=rem-(r1-l1+1);
                r2rem=need-1;
            }
            if(l2rem==-1)
            {
                if(l1rem==0)
                    vv=h[r1rem];
                else
                    vv=(h[r1rem]-(h[l1rem-1]*p[r1rem-l1rem+1])%mod);

                if(vv<0)vv+=mod;
            }
            else
            {

                int value1=h[r2rem];
                int value2=h[r1rem]-((h[l1rem-1]*p[r1rem-l1rem+1])%mod);
                if(value2<0)value2+=mod;
                vv=(value1+ (value2*p[r2rem+1])%mod)%mod;
            }
            if(rem==0)vv=0;
            ans=((ans*p[rem])%mod+vv)%mod;
            mp[(int)ans]++;
        }
        else
            mp[(int)value]++;
    }

}

signed main()
{

    IOS
    cin>>n>>m>>k;
    vector<vector<char>> grid(n,vector<char>(m));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>grid[i][j];
        }
    }
    p[0]=1;
    for(int i=1; i<=n*m+10; i++)
    {
        p[i]=(p[i-1]*b)%mod;
    }

    for(int i=0; i<n; i++)
    {
        string x;
        for(int j=0; j<m; j++)
        {
            x.push_back(grid[i][j]);
        }
        roh(x);
        x.clear();
        for(int j=m-1; j>=0; j--)
        {
            x.push_back(grid[i][j]);
        }
        roh(x);
    }
    string x;
    for(int j=0; j<m; j++)
    {
        x.clear();
        for(int i=0; i<n; i++)
        {
            x.push_back(grid[i][j]);
        }

        roh(x);
        x.clear();
        for(int i=n-1; i>=0; i--)
        {
            x.push_back(grid[i][j]);
        }

        roh(x);
    }


    vector<vector<int>> vis(n,vector<int>(m));

    int cnt=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(!vis[i][j])
            {
                cnt++;
                string x;
                vis[i][j]=true;
                x.push_back(grid[i][j]);
                int ii=(i-1+n)%n;
                int jj=(j-1+m)%m;
                while(ii!=i || jj!=j)
                {
                    vis[ii][jj]=true;
                    x.push_back(grid[ii][jj]);
                    ii=(ii-1+n)%n;
                    jj=(jj-1+m)%m;
                }
                roh(x);
                reverse(x.begin(),x.end());
                roh(x);
            }
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            vis[i][j]=0;
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(!vis[i][j])
            {
                string x;
                vis[i][j]=true;
                x.push_back(grid[i][j]);
                int ii=(i-1+n)%n;
                int jj=(j+1+m)%m;
                while(ii!=i || jj!=j)
                {
                    vis[ii][jj]=true;
                    x.push_back(grid[ii][jj]);
                    ii=(ii-1+n)%n;
                    jj=(jj+1+m)%m;
                }
                roh(x);
                reverse(x.begin(),x.end());
                roh(x);
            }
        }
    }

    int num,den;
    num=0;
    den=n*m*8*n*m*8;
    for(auto [a,b]:mp)
    {
        num+= (b*b);
    }
    int g=gcd(num,den);

    cout<<(num/g)<<"/"<<(den/g);

}

• Subtask 1: 160 / 160