Submission #845576

#	Time	Username	Problem	Language	Result	Execution time	Memory
845576		vjudge1	Trener (COCI20_trener)	C++17	110 / 110	956 ms	12820 KiB

trener

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
array<int,3> cs = {23+8,23+14,23+18};
array<int,3> mods = {232323233,232323323,323232323};
array<int,3> hashle(string str){
	array<int,3> ret={0,0,0};
	array<int,3> co={1,1,1};
	for (int i = 0; i < str.length(); i++){
		for (int j = 0; j < 3; j++){
			ret[j]+=co[j]*str[i];
			ret[j]%=mods[j];
			co[j]*=cs[j];
			co[j]%=mods[j];
		}
	}
	return ret;
}
int32_t main(){
	int n,k;
	cin>>n>>k;
	vector<vector<int>> dp(n,vector<int>(k,0));
	vector<vector<string>> _arr(n,vector<string>(k));
	for (int i = 0; i < n; i++){
		for (int j = 0; j < k; j++){
			cin>>_arr[i][j];
		}
	}
	vector<vector<array<int,3>>> sag(n,vector<array<int,3>>(k));
	vector<vector<array<int,3>>> sol(n,vector<array<int,3>>(k));
	vector<vector<array<int,3>>> hash(n,vector<array<int,3>>(k));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < k; j++){
			hash[i][j]=hashle(_arr[i][j]);
			if (i){
				sag[i][j]=hashle(_arr[i][j].substr(1,i));
				sol[i][j]=hashle(_arr[i][j].substr(0,i));
			}
		}
	}
	for (int node = n-1; node >= 0; node--){
		for (int flag = 0; flag < k; flag++){
			if (node==n-1){
				dp[node][flag]=1;
				continue;
			}
			for (int i = 0; i < k; i++){
				if (hash[node][flag]==sol[node+1][i] || hash[node][flag]==sag[node+1][i]){
					dp[node][flag]+=dp[node+1][i];
					dp[node][flag]%=MOD;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < k; i++){
		ans+=dp[0][i];
		ans%=MOD;
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

trener.cpp: In function 'std::array<long long int, 3> hashle(std::string)':
trener.cpp:10:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for (int i = 0; i < str.length(); i++){
      |                  ~~^~~~~~~~~~~~~~

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