oj.uz

Submission #238468

# Submission time Handle Problem Language Result Execution time Memory
238468 2020-06-11T12:55:15 Z akat Trener (COCI20_trener) C++14
110 / 110
 1547 ms 27932 KB 
    #include<bits/stdc++.h>
    #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 7 ms 3456 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5376 KB Output is correct
2 Correct 24 ms 5376 KB Output is correct
3 Correct 25 ms 5376 KB Output is correct
4 Correct 22 ms 5376 KB Output is correct
5 Correct 24 ms 5368 KB Output is correct
6 Correct 24 ms 5376 KB Output is correct
7 Correct 23 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 7 ms 3456 KB Output is correct
5 Correct 23 ms 5376 KB Output is correct
6 Correct 24 ms 5376 KB Output is correct
7 Correct 25 ms 5376 KB Output is correct
8 Correct 22 ms 5376 KB Output is correct
9 Correct 24 ms 5368 KB Output is correct
10 Correct 24 ms 5376 KB Output is correct
11 Correct 23 ms 5376 KB Output is correct
12 Correct 1446 ms 27852 KB Output is correct
13 Correct 1403 ms 27932 KB Output is correct
14 Correct 1423 ms 27768 KB Output is correct
15 Correct 1480 ms 27896 KB Output is correct
16 Correct 1168 ms 27896 KB Output is correct
17 Correct 1452 ms 27692 KB Output is correct
18 Correct 1427 ms 27768 KB Output is correct
19 Correct 1439 ms 27784 KB Output is correct
20 Correct 1483 ms 27768 KB Output is correct
21 Correct 1547 ms 27640 KB Output is correct
22 Correct 1218 ms 27640 KB Output is correct