Submission #373725

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
373725	2021-03-05T13:58:37 Z	morato	Mate (COCI18_mate)	C++17	100 / 100	829 ms	13412 KB

mate

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int sum[2][2001][26], ans[2001][26][26]; // sum[sz][x] = soma dos dp[sz][K][x]

int mod(int a, int b) {
	a %= b;
	if (a < 0) a += b;
	return a;
}

void add_self(int& a, int b) {
	a = mod(a + b, MOD);
}

/*
	dp[ t ][ x ][ y ] = numero de sequencias de tamanho t ate r que terminam em xy
	calculo pra cada r ^ e somo em sum[ t ][ x ][ y ]
*/

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string str; cin >> str;
	int n = (int) str.size();
	sum[0][0][0] = 1;
	for (int r = 0; r < n; r++) {
		// vou adicionar o str[r] para buildar um novo bloco
		for (int sz = 0; sz <= r; sz++) {
			// para cada tamanho
			for (int x = 0; x < 26; x++) {
				// adiciono as strings que terminam em [str[r] - 'a'] na soma do prefixo
				add_self(sum[!(r & 1)][sz + 1][str[r] - 'a'], sum[r & 1][sz][x]);
				// adiciono as strings que terminam em x do prefixo anterior no novo prefixo
				add_self(sum[!(r & 1)][sz][x], sum[r & 1][sz][x]);
				// soma de prefixo de [sz][x][y]
				add_self(ans[sz + 1][x][str[r] - 'a'], sum[r & 1][sz][x]);
				sum[r & 1][sz][x] = 0;
			}
		}
	}
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int l; cin >> l;
		string suffix; cin >> suffix;
		//long long ans = 0;
		cout << ans[l][suffix[0] - 'a'][suffix[1] - 'a'] << '\n';
	}	
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	748 KB	Output is correct
2	Correct	5 ms	620 KB	Output is correct
3	Correct	8 ms	620 KB	Output is correct
4	Correct	10 ms	748 KB	Output is correct
5	Correct	50 ms	2668 KB	Output is correct
6	Correct	58 ms	2924 KB	Output is correct
7	Correct	36 ms	2540 KB	Output is correct
8	Correct	33 ms	2412 KB	Output is correct
9	Correct	785 ms	13292 KB	Output is correct
10	Correct	829 ms	13412 KB	Output is correct