oj.uz

답안 #373694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373694 2021-03-05T12:51:48 Z morato Mate (COCI18_mate) C++17
40 / 100
 36 ms 18412 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long dp[55][55][26][26], sum[55][55][26]; // sum[sz][x] = soma dos dp[sz][K][x]

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

void add_self(long long& a, long long 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();
	dp[0][0][0][0] = 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++) {
				// para cada x (segundo negocio)
				add_self(dp[r + 1][sz + 1][x][str[r] - 'a'], sum[r][sz][x]);
				add_self(sum[r + 1][sz + 1][str[r] - 'a'], dp[r + 1][sz + 1][x][str[r] - 'a']);
				add_self(sum[r + 1][sz][x], sum[r][sz][x]);
				//nsum[sz + 1]
			}
		}
	}
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int l; cin >> l;
		string suffix; cin >> suffix;
		long long ans = 0;
		for (int r = 2; r <= n; r++) {
			//cerr << "R = " << r << " -> " << dp[r][l][suffix[0] - 'a'][suffix[1] - 'a'] << '\n';
			add_self(ans, dp[r][l][suffix[0] - 'a'][suffix[1] - 'a']);
		}
		cout << ans << '\n';
	}	
	return 0;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 7276 KB Output is correct
2 Correct 21 ms 6636 KB Output is correct
3 Correct 22 ms 6124 KB Output is correct
4 Correct 33 ms 6764 KB Output is correct
5 Runtime error 22 ms 18412 KB Execution killed with signal 11
6 Runtime error 21 ms 18412 KB Execution killed with signal 11
7 Runtime error 22 ms 18412 KB Execution killed with signal 11
8 Runtime error 22 ms 18412 KB Execution killed with signal 11
9 Runtime error 21 ms 18412 KB Execution killed with signal 11
10 Runtime error 21 ms 18412 KB Execution killed with signal 11