Submission #1270317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270317		newbie_t	Osmosmjerka (COCI17_osmosmjerka)	C++20	160 / 160	2057 ms	39568 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;

// our goal is to generate all the possible unique strings and their counts

// i generate all the possible strings, but string can go up to 1e9 so I generate only the pattern
// by pattern I mean for example "abcabc" this string pattern is "abc"
// so we can just generate the pattern and store their values in a map however there is a problem
// the pattern generated are not all of the same size so lets say that k is very big and we only generated the patterns
// we can have a pattern of "aba"   and another of "ab"
// we will miss that this "ab" is the same as this "aba" because we didn't continue and we had to stop when we are just repeating the pattern
// so the solution is to find the pattern and calculate it's hash function and calculate it's k-length version by just calculating a geometric series

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;
}
int hash_len(int start,vector<__int128> &h,int len) // this function just calculate the hash for the pattern
{
    int sz=h.size();
    int l1,l2,r1,r2;
    l1=l2=r1=r2=-1;
    l1=start;
    r1 =min(sz-1,start+len-1);
    if(r1-l1+1 <len)
    {
        l2=0;
        int need=len-(r1-l1+1);
        r2=need-1;
    }
    int value=0;
    if(l2==-1)
    {
        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[r1]-((h[l1-1]*p[r1-l1+1])%mod);
        int value2=h[r2];
        if(value1<0)value1+=mod;
        value=((value1*p[r2+1]%mod)+value2)%mod;
    }
    return value;
}

void roh(string x)              // this function generates the pattern and calculate it's k-hashed version with geometric series
{
    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;

    for(int i=0; i<x.size(); i++)
    {
        int value=hash_len(i,h,sz);
        if(sz!=k)
        {                // geometric series
            int rem=k%sz;
            int q=k/sz;
            int r=p[sz];
            __int128 num=1-(pows(r,q))+mod;
            num=(value*num)%mod;
            __int128 den=pows((1-r+mod),mod-2);
            __int128 ans=(num*den)%mod;

            value=ans;
            if(rem!=0)
            {
                int hash_of_reminder=hash_len(i,h,rem);
                value=((ans*p[rem])%mod+hash_of_reminder)%mod;
            }

        }

        mp[value]++;
    }

}

int vis[502][502];
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;

//example:
    //abc
    //def

    //lets say we want to generate the strings from going to the right only in the first row  then we         will make "abc"
    // now this "abc"  can be used to calculate the pattern for the whole row for a and b and for c
    //for b is "bca"
    //for c it's cab
    //so it's just a cycles from the original string "abc"

    // also if I want to go the other direction (left) I can just inverse the string and make it cba


    int di[]= {-1,-1,0,1};  // so here i only go 4 directions because I will reverse the string generated which will just represent the other direction
    int dj[]= {1,-1,1,0};
    for(int d=0; d<4; d++)
    {
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(!vis[i][j])
                {
                    vis[i][j]=true;
                    string x;
                    x.push_back(grid[i][j]);
                    int ii,jj;
                    ii=i;
                    jj=j;
                    while(true) // keep moving till you get back to where you started
                    {
                        ii=(ii+di[d]+n)%n;
                        jj=(jj+dj[d]+m)%m;
                        if(ii==i && jj==j)break;
                        vis[ii][jj]=true;
                        x.push_back(grid[ii][jj]);
                    }
                    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