제출 #238440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238440		MishoKostov	Trener (COCI20_trener)	C++14	55 / 110	2080 ms	7504 KiB

trener

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

using namespace std;

const int nmax=2048, mod=1000000007;
int pi[nmax];
string a[64][nmax];
int n, m;
int r[nmax][nmax];

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;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin>>n>>m;
	for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j) cin>>a[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(kmp(a[i][j], a[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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55