oj.uz

Submission #238450

# Submission time Handle Problem Language Result Execution time Memory
238450 2020-06-11T11:40:45 Z MishoKostov Trener (COCI20_trener) C++14
22 / 110
 21 ms 4480 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 4480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3456 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Incorrect 21 ms 4480 KB Output isn't correct
6 Halted 0 ms 0 KB -