oj.uz

Submission #44505

# Submission time Handle Problem Language Result Execution time Memory
44505 2018-04-02T17:35:11 Z MatheusLealV Mate (COCI18_mate) C++17
100 / 100
 1708 ms 55672 KB 
#include <bits/stdc++.h>
#define N 2005
#define mod (1000000000 + 7)
using namespace std;
typedef long long ll;
 
string s;
 
int n, q, qtd[30][N];
 
ll dp[N][30][30], ch[N][N];
 
vector<int> pos[30];
 
ll choose(int a, int b)
{
	if(a == b || b == 0) return 1;
 
	if(b == 1) return a;
 
	if(b > a) return 0;
 
	if(ch[a][b] != -1) return ch[a][b];
 
	return ch[a][b] = (choose(a - 1, b - 1) + choose(a - 1, b))%mod;
}
 
void solve(int a, int b)
{
	for(int len = 1; len <= n; len ++)
	{
		for(int i = 0; i < pos[a].size(); i++)
		{
			int x = pos[a][i];
 
			dp[len][a][b] += ((ll)qtd[b][x + 1] * choose(x - 1, len - 2))%mod;
 
			dp[len][a][b] %= mod;
		}
	}
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>s;
 
	n = s.size();
 
	for(int c = 0; c < 30; c++)
		for(int i = n; i >= 1; i--)
			qtd[c][i] = qtd[c][i + 1] + (s[i - 1] - 'a' == c);
 
	for(int i = 1; i <= n; i++) pos[ s[i - 1] - 'a'].push_back(i);
 
	memset(ch, -1, sizeof ch);
 
	for(int a = 0; a < 30; a++)
		for(int b = 0; b < 30; b++)
			solve(a, b);
		
	cin>>q;
 
	while(q--)
	{
		int l; string aux;
 
		cin>>l>>aux;
 
		int a = aux[0] - 'a', b = aux[1] - 'a';
 
		cout<<dp[l][a][b]<<"\n";
	}
}

Compilation message

mate.cpp: In function 'void solve(int, int)':
mate.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pos[a].size(); i++)
                  ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32504 KB Output is correct
2 Correct 29 ms 32640 KB Output is correct
3 Correct 30 ms 32908 KB Output is correct
4 Correct 34 ms 33296 KB Output is correct
5 Correct 79 ms 35888 KB Output is correct
6 Correct 86 ms 37004 KB Output is correct
7 Correct 76 ms 37668 KB Output is correct
8 Correct 68 ms 38220 KB Output is correct
9 Correct 1591 ms 55652 KB Output is correct
10 Correct 1708 ms 55672 KB Output is correct