Submission #44505

#	Time	Username	Problem	Language	Result	Execution time	Memory
44505		MatheusLealV	Mate (COCI18_mate)	C++17	100 / 100	1708 ms	55672 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[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 (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: 100 / 100