Submission #238450

#	Time	Username	Problem	Language	Result	Execution time	Memory
238450		MishoKostov	Trener (COCI20_trener)	C++14	22 / 110	21 ms	4480 KiB

trener

#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
#define endl "\n"

using namespace std;

const int nmax=2048, mod=1000000007;
int pi[nmax];
vector<int> a[64][nmax];
int n, m;
int r[nmax][nmax];
int pw[64];
int base=29;


bool kmp(string s, string b)
{
    int x=s.size();
    s+="#"+b;
    //cout<<s<<endl;
    int sz=s.size();
    for(int i=1; i<sz; ++i)
    {
        int j=pi[i-1];
        while(j>0&&s[i]!=s[j]) j=pi[j-1];
        if(s[i]==s[j]) j++;
        pi[i]=j;
        if(pi[i]==x) return true;
    }
    return false;
}

void hashing_prefix(string s, int i, int j)
{
    a[i][j].push_back(0);
    s="%"+s;
    //cout<<s<<endl;
    for(int k=1; k<(int)s.size(); ++k)
    {
        a[i][j].push_back(a[i][j][k-1]*base+(s[k]-'a'+1));
        a[i][j][k]%=mod;
    }
    //for(int k=0; k<(int)a[i][j].size(); ++k) cout<<a[i][j][k]<<" ";
    //cout<<endl;
}

bool rabin_karp(int i, int j, int i1, int j1)
{
    long long h=a[i][j][a[i][j].size()-1];
    //cout<<"h = "<<h<<endl;
    //cout<<(int)a[i][j].size()<<" "<<(int)a[i1][j1].size()<<endl;
    for(int x=1, y=(int)a[i][j].size()-1; y<(int)a[i1][j1].size(); ++x, ++y)
    {
        //cout<<"CONCALA   "<<a[i1][j1][y]<<" "<<a[i1][j1][x-1]<<endl;
        long long phash=a[i1][j1][y]-a[i1][j1][x-1]*pw[y-x+1];
        //cout<<"ann  "<<phash<<" "<<h<<endl;
        phash=(phash%mod+mod)%mod;
        if(h==phash) return true;
    }
    return false;
}

int main()
{
	pw[0]=1;
	for(int i=1; i<=50; ++i) pw[i]=pw[i-1]*base, pw[i]%=mod;


	string s;
	cin>>n>>m;
	for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
        {
            cin>>s;
            hashing_prefix(s, i, j);
        }
    if(n==1) cout<<m<<endl, exit(0);

    for(int i=0; i<m; ++i) r[0][i]=1;
    for(int i=0; i<n-1; ++i)
        for(int j=0; j<m; ++j)
            for(int k=0; k<m; ++k)
            {
                if(rabin_karp(i, j, i+1, k)) r[i+1][k]+=r[i][j], r[i+1][k]%=mod;
            }
    //for(int i=1; i<n; ++i, cout<<endl)
    //    for(int j=0; j<m; ++j) cout<<r[i][j]<<" ";
    int sum=0;
    for(int i=0; i<m; ++i) sum+=r[n-1][i], sum%=mod;
    cout<<sum<<endl;
 	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55