oj.uz

Submission #238452

# Submission time Handle Problem Language Result Execution time Memory
238452 2020-06-11T11:42:47 Z MishoKostov Trener (COCI20_trener) C++14
110 / 110
 1144 ms 28072 KB 
#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.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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5376 KB Output is correct
2 Correct 21 ms 5376 KB Output is correct
3 Correct 21 ms 5368 KB Output is correct
4 Correct 20 ms 5376 KB Output is correct
5 Correct 21 ms 5376 KB Output is correct
6 Correct 22 ms 5376 KB Output is correct
7 Correct 21 ms 5376 KB Output is correct

Subtask #3
55.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 Correct 21 ms 5376 KB Output is correct
6 Correct 21 ms 5376 KB Output is correct
7 Correct 21 ms 5368 KB Output is correct
8 Correct 20 ms 5376 KB Output is correct
9 Correct 21 ms 5376 KB Output is correct
10 Correct 22 ms 5376 KB Output is correct
11 Correct 21 ms 5376 KB Output is correct
12 Correct 1081 ms 27784 KB Output is correct
13 Correct 1088 ms 27896 KB Output is correct
14 Correct 1099 ms 27768 KB Output is correct
15 Correct 1105 ms 27768 KB Output is correct
16 Correct 837 ms 28072 KB Output is correct
17 Correct 1121 ms 27772 KB Output is correct
18 Correct 1111 ms 27640 KB Output is correct
19 Correct 1116 ms 27796 KB Output is correct
20 Correct 1090 ms 27896 KB Output is correct
21 Correct 1144 ms 27824 KB Output is correct
22 Correct 830 ms 27768 KB Output is correct