Submission #44504

#	Time	Username	Problem	Language	Result	Execution time	Memory
44504		MatheusLealV	Mate (COCI18_mate)	C++17	0 / 100	111 ms	65040 KiB

mate

#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[30][30][N], 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 (stderr)

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: 0 / 100