제출 #238468

#제출 시각아이디문제언어결과실행 시간메모리
238468akatTrener (COCI20_trener)C++14
110 / 110
1547 ms27932 KiB
    #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;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...