Submission #1097395

#TimeUsernameProblemLanguageResultExecution timeMemory
10973950pt1mus23Trener (COCI20_trener)C++14
110 / 110
631 ms7280 KiB
#include <bits/stdc++.h> using namespace std; #define int unsigned long long #define ins insert #define pb push_back #define putr(x) cout<<x<<endl;return; #define all(x) x.begin(),x.end() #define endl '\n' #define _ << " " << const int mod = 23157982937,mod2=3615727, mod3=1e9+7, sze = 2e3, inf = 1e9, L = 30 ; mt19937 rng(time(0)); int MOD,prim; int dp[55][sze]; int pw[sze]; int pw2[sze]; pair<int,pair<int,int>> hashle(string &s,int &n){ pair<int,pair<int,int>> hash; int h1 = 0; int pref =0; int suff =0; for(int i=0;i<n;i++){ if(i>0){ suff = ((suff + (s[i]-'a' +1)*1LL * pw[i-1] % MOD + MOD)%MOD + MOD ) % MOD; } if(i<n-1){ pref = ((pref + (s[i]-'a' +1) * 1LL * pw[i] % MOD + MOD)%MOD + MOD)%MOD ; } h1 = ((h1 + (s[i]-'a' +1) * 1LL * pw[i] %MOD + MOD) %MOD + MOD )% MOD; // cout<<s<< " "<< h1<<endl; // cout<<h1<<endl; } hash.first = h1; hash.second = {pref,suff}; return hash; } pair<int,pair<int,int>> hashle2(string &s,int &n){ pair<int,pair<int,int>> hash; int h1 = 0; int pref =0; int suff =0; for(int i=0;i<n;i++){ if(i>0){ suff = (suff + (s[i]-'a' +1)*1LL * pw2[i-1] % mod + mod)%mod; } if(i<n-1){ pref = (pref + (s[i]-'a' +1) * 1LL * pw2[i] % mod + mod)%mod ; } h1 = (h1 + (s[i]-'a' +1) * 1LL * pw2[i] %mod + mod) %mod; // cout<<s<< " "<< h1<<endl; // cout<<h1<<endl; } hash.first = h1; hash.second = {pref,suff}; return hash; } int check(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b , pair<int,pair<int,int>> a2, pair<int,pair<int,int>> b2 ){ // cout<<a.second.first<<" , "<<a.second.second<<" "<<b.first<<endl; return ((a.second.first == b.first && a2.second.first == b2.first )|| ( a.second.second == b.first && a2.second.second == b2.first) ); } void _0x0(){ MOD = rng(); prim = rng(); pw[0]=1; pw2[0]=1; for(int i=1;i<sze;i++){ pw[i]=(pw[i-1] * 1LL * prim + MOD )%MOD; pw2[i]=(pw2[i-1] * 1LL * mod2 + mod )%mod; } int n,k; cin>>n>>k; vector< vector< pair< pair<int,pair<int,int>>, pair<int,pair<int,int>>> > > lst(n+10); // string s="aaa"; // int n = 3; // cout<<hashle(s,n).second.first <<" "<<hashle(s,n).second.second <<endl; string s; for(int i=1;i<=n;i++){ for(int j=0;j<k;j++){ cin>>s; auto h = hashle(s,i); auto h2 = hashle2(s,i); // cout<<s<<" => "<<h.first<<" , "<<h.second.first<<" , "<<h.second.second<<endl; lst[i].pb({h,h2}); } } for(int j=0;j<k;j++){ dp[1][j]=1; } // cout<<check(lst[2][0],lst[1][0])<<endl; for(int i=2;i<=n;i++){ for(int j=0;j<k;j++){ for(int p=0;p<k;p++){ if(check(lst[i][j].first, lst[i-1][p].first, lst[i][j].second, lst[i-1][p].second)){ // cout<<i<<" => "<<j<<endl; dp[i][j] = (dp[i][j] + dp[i-1][p] )%mod3 ; } } } } int ans=0; for(int i=0;i<k;i++){ ans=(ans + dp[n][i] )%mod3; } putr(ans); } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; // cin>>tt; while(tt--){ _0x0(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...