Submission #48410

#	Time	Username	Problem	Language	Result	Execution time	Memory
48410		luciocf	Mate (COCI18_mate)	C++14	100 / 100	637 ms	42656 KiB

mate

#include <bits/stdc++.h>

using namespace std;

/*
1) Precalcular a frequência de sufixo de cada letra -> O(n)
2) Precalcular x^(MOD-2) (1 <= x <= n) -> O(n log MOD)
3) Precalcular x escolhe y (y <= x <= n) -> O(n²)
4) Solve! -> O(n²)
*/

const int MAXN = 2e3+10;
const int MOD = 1e9+7;

typedef long long ll;

int n, q;
ll freq[MAXN][30], choose[MAXN][MAXN], pot[MAXN];
ll ans[MAXN][30][30];
string s;

ll Pot(ll b, ll e)
{
    if (e == 0LL) return 1LL;

    ll x = Pot(b, e/2);

    if (e%2 == 0LL) return (x*x)%MOD;
    else return (((b*x)%MOD)*x)%MOD;
}

void pre_freq(void)
{
    for (int i = n; i >= 1; i--)
    {
        for (int j = 1; j <= 26; j++)
        {
            if ((int) s[i-1]-(int)'a'+1 == j)
                freq[i][j] = freq[i+1][j]+1LL;
            else
                freq[i][j] = freq[i+1][j];
        }
    }
}

void pre_pot(void)
{
    for (ll i = 0LL; i <= n; i++)
        pot[i] = Pot(i, MOD-2)%MOD;
}

void pre_choose(void)
{
    for (int i = 0; i <= n; i++)
    {
        choose[i][0] = 1LL;
        for (int j = 1; j <= i; j++)
        {
            choose[i][j] = (choose[i][j-1]*(i-j+1))%MOD;
            choose[i][j] = (choose[i][j]*pot[j])%MOD;
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> s;
    n = s.size();

    pre_freq();
    pre_pot();
    pre_choose();

    for (int i = 1; i <= n; i++)
    {
        for (int j = 2; j <= i+1; j++)
        {
            for (int l = 1; l <= 26; l++)
            {
                int a1 = (int) s[i-1]-(int)'a'+1;
                ans[j][a1][l] = (ans[j][a1][l]+(freq[i+1][l]*choose[i-1][j-2])%MOD)%MOD;
            }
        }
    }
    cin >> q;
    while (q--)
    {
        int m;
        char a1, a2;
        cin >> m >> a1 >> a2;

        int b1 = (int) a1-(int)'a'+1, b2 = (int)a2-(int)'a'+1;
        cout << ans[m][b1][b2] << "\n";
    }
}

• Subtask 1: 100 / 100