oj.uz

Submission #48410

# Submission time Handle Problem Language Result Execution time Memory
48410 2018-05-12T19:55:48 Z luciocf Mate (COCI18_mate) C++14
100 / 100
 637 ms 42656 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1016 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1036 KB Output is correct
4 Correct 9 ms 1036 KB Output is correct
5 Correct 34 ms 3644 KB Output is correct
6 Correct 39 ms 3764 KB Output is correct
7 Correct 32 ms 3828 KB Output is correct
8 Correct 28 ms 3828 KB Output is correct
9 Correct 578 ms 42576 KB Output is correct
10 Correct 637 ms 42656 KB Output is correct