Submission #445089

#	Time	Username	Problem	Language	Result	Execution time	Memory
445089		Tahmid690	Trener (COCI20_trener)	C++14	110 / 110	1302 ms	34180 KiB

trener

// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
 
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
                                                     
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 */
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef map<int,int> mpi;
typedef map<ll,ll> mpl;
typedef unordered_map<int,int> umpi;
typedef unordered_map<ll,ll> umpl;
 
#define ump unordered_map
#define mod 1000000007
#define inf 1000000000000000006
#define infi 1000000009
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define pi acos(-1.0)
#define dec(n) fixed << setprecision(n)
#define N 200005
//#define int long long



struct ss{
	ll hash[55];
};
ll bigmod(ll a,ll b){
    if(b==0) return 1;
    ll ret=bigmod(a,b/2);
    ret*=ret;
    ret%=mod;
    if(b%2==1) ret*=a;
    return ret%mod;
    
}

vector<ss> v[55];
string s;
int n,k;
ll dp[1505][55],inv;
ll DP(int p,int x){
	if(x==n) return 1;
	if(dp[p][x]!=-1) return dp[p][x];
	ll ret=0;
	for(int i=0;i<k;i++){
		if(v[x][i].hash[x]==v[x-1][p].hash[x] || ((((v[x][i].hash[x+1]-v[x][i].hash[1])*inv)+mod)%mod)==v[x-1][p].hash[x]) ret+=DP(i,x+1);
		ret%=mod;
	}
	return dp[p][x]=ret;
}
void solve(){
	cin >> n >> k;
	for(int i=0;i<n;i++){
		v[i].resize(k);
		for(int j=0;j<k;j++){
			cin >> s;
			ss tmp;
			ll p=31,hashval=0,pw=1;
		    for(int k=0;k<s.size();k++){
        		hashval=(hashval+(s[k]-'a'+1)*pw)%mod;
        		pw=(pw*p)%mod;
        		tmp.hash[k+1]=hashval;
    		}
			v[i][j]=tmp;
		}
	}
	inv=bigmod(31,mod-2);
	memset(dp,-1,sizeof dp);
	ll ans=0;
	for(int i=0;i<k;i++){
		ans+=DP(i,1);
		ans%=mod;
	}
	cout << ans << endl;
	
}

signed main(){
    fastio;
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    int T=1,cs=0;
    //cin >> T;
    while(T--){
        //cout << "Case " << ++cs << ":" << " " ; 
    	solve();
    } 
}

Compilation message (stderr)

trener.cpp: In function 'void solve()':
trener.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       for(int k=0;k<s.size();k++){
      |                   ~^~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:103:13: warning: unused variable 'cs' [-Wunused-variable]
  103 |     int T=1,cs=0;
      |             ^~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55