Submission #238452

#	Time	Username	Problem	Language	Result	Execution time	Memory
238452		MishoKostov	Trener (COCI20_trener)	C++14	110 / 110	1144 ms	28072 KiB

trener

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

using namespace std;

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


bool kmp(string s, string b)
{
    long long x=s.size();
    s+="#"+b;
    //cout<<s<<endl;
    long long sz=s.size();
    for(long long i=1; i<sz; ++i)
    {
        long long 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, long long i, long long j)
{
    a[i][j].push_back(0);
    s="%"+s;
    //cout<<s<<endl;
    for(long long k=1; k<(long long)s.size(); ++k)
    {
        a[i][j].push_back(a[i][j][k-1]*base+(s[k]-'a'+1));
        a[i][j][k]%=mod;
    }
    //for(long long k=0; k<(long long)a[i][j].size(); ++k) cout<<a[i][j][k]<<" ";
    //cout<<endl;
}

bool rabin_karp(long long i, long long j, long long i1, long long j1)
{
    long long h=a[i][j][a[i][j].size()-1];
    //cout<<"h = "<<h<<endl;
    //cout<<(long long)a[i][j].size()<<" "<<(long long)a[i1][j1].size()<<endl;
    for(long long x=1, y=(long long)a[i][j].size()-1; y<(long long)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(long long i=1; i<=50; ++i) pw[i]=pw[i-1]*base, pw[i]%=mod;


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

    for(long long i=0; i<m; ++i) r[0][i]=1;
    for(long long i=0; i<n-1; ++i)
        for(long long j=0; j<m; ++j)
            for(long long 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(long long i=1; i<n; ++i, cout<<endl)
    //    for(long long j=0; j<m; ++j) cout<<r[i][j]<<" ";
    long long sum=0;
    for(long long i=0; i<m; ++i) sum+=r[n-1][i], sum%=mod;
    cout<<sum<<endl;
 	return 0;
}

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