oj.uz

답안 #335223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335223 2020-12-11T15:37:14 Z ronnith Trener (COCI20_trener) C++14
110 / 110
 1484 ms 78072 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 5484 KB Output is correct
2 Correct 18 ms 5484 KB Output is correct
3 Correct 17 ms 5484 KB Output is correct
4 Correct 16 ms 5504 KB Output is correct
5 Correct 18 ms 5484 KB Output is correct
6 Correct 19 ms 5484 KB Output is correct
7 Correct 16 ms 5484 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 18 ms 5484 KB Output is correct
6 Correct 18 ms 5484 KB Output is correct
7 Correct 17 ms 5484 KB Output is correct
8 Correct 16 ms 5504 KB Output is correct
9 Correct 18 ms 5484 KB Output is correct
10 Correct 19 ms 5484 KB Output is correct
11 Correct 16 ms 5484 KB Output is correct
12 Correct 1463 ms 77836 KB Output is correct
13 Correct 1452 ms 77980 KB Output is correct
14 Correct 1462 ms 77844 KB Output is correct
15 Correct 1466 ms 77956 KB Output is correct
16 Correct 974 ms 77932 KB Output is correct
17 Correct 1469 ms 78072 KB Output is correct
18 Correct 1481 ms 78060 KB Output is correct
19 Correct 1484 ms 77932 KB Output is correct
20 Correct 1467 ms 77932 KB Output is correct
21 Correct 1460 ms 77940 KB Output is correct
22 Correct 991 ms 77804 KB Output is correct