Submission #238440

#TimeUsernameProblemLanguageResultExecution timeMemory
238440MishoKostovTrener (COCI20_trener)C++14
55 / 110
2080 ms7504 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...