Submission #335223

#	Time	Username	Problem	Language	Result	Execution time	Memory
335223		ronnith	Trener (COCI20_trener)	C++14	110 / 110	1484 ms	78072 KiB

trener

#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i = a;i < b;i ++)
#define sz(a) int((a).size())
#define trav(a, b) for(auto a : b)
#define mk make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

ll modF = 1e9 + 7;

#define RANDOM chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()
ll mult(ll a,ll b){return (a * b) % modF;}
ll add(ll a,ll b){return (a + b) % modF;}
ll sub(ll a,ll b){return (a - b + modF) % modF;}

struct hassh{
	ll h1,h2;
	hassh():hassh(0,0){}
	hassh(ll h,ll hh):h1(h),h2(hh){}
	bool operator<(const hassh& b) const {
		if(h1 == b.h1)return h2 < b.h2;
		return h1 < b.h1;
	}
	bool operator==(const hassh& b) const {
		if(h1 == b.h1 and h2 == b.h2) return true;
		return false;
	}
};
ll b1 = (RANDOM) % modF;
ll b2 = (RANDOM) % modF;
struct StringHash{
	ll N;
	vector<ll> pw1, pw2;vector<hassh> hsh;
	StringHash(){}
	StringHash(const string& s){
		N = sz(s);
		hsh.assign(N,hassh(0,0));pw1.assign(N + 1,1);pw2.assign(N + 1,1);
		FOR(i,1,N + 1){
			pw1[i] = mult(b1, pw1[i - 1]);
			pw2[i] = mult(b2, pw2[i - 1]);
		}
		FOR(i,0,N){
			if(i == 0){
				hsh[i].h1 = s[i];hsh[i].h2 = s[i];
			} else {
				hsh[i].h1 = add(mult(hsh[i - 1].h1, b1), s[i]);hsh[i].h2 = add(mult(hsh[i - 1].h2, b2), s[i]);
			}
		}
	}
	hassh find_hash(ll l,ll r){
		ll H1 = hsh[r].h1, H2 = hsh[r].h2;
		if(l != 0){
			H1 = sub(H1, mult(hsh[l - 1].h1, pw1[r - l + 1])), H2 = sub(H2, mult(hsh[l - 1].h2, pw2[r - l + 1]));
		}
		return hassh(H1,H2);
	}
};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<vector<string>> a(n, vector<string>(k));
	vector<vector<StringHash>> sh(n, vector<StringHash>(k));
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < k;j ++){
			cin >> a[i][j];
			sh[i][j] = StringHash(a[i][j]);
		}
	}
	ll dp[n][k];
	ll ans = 0;
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < k;j ++){
			dp[i][j] = 0;
			if(i == 0){
				dp[i][j] = 1;
			} else {
				for(int it = 0;it < k;it ++){
					if(sh[i][j].find_hash(0, i - 1) == sh[i - 1][it].find_hash(0,i - 1) or sh[i][j].find_hash(1, i) == sh[i - 1][it].find_hash(0,i - 1)){
						dp[i][j] = (dp[i][j] + dp[i - 1][it]) % modF;
					}
				}
			}
			if(i == n - 1)ans = (ans + dp[i][j]) % modF;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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