oj.uz

Submission #48407

# Submission time Handle Problem Language Result Execution time Memory
48407 2018-05-12T19:43:40 Z luciocf Mate (COCI18_mate) C++14
0 / 100
 535 ms 55892 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*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] += (freq[i+1][l]*choose[i-1][j-2])%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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1272 KB Output isn't correct
2 Incorrect 6 ms 1532 KB Output isn't correct
3 Incorrect 6 ms 1652 KB Output isn't correct
4 Incorrect 9 ms 1900 KB Output isn't correct
5 Incorrect 35 ms 5712 KB Output isn't correct
6 Incorrect 58 ms 6676 KB Output isn't correct
7 Incorrect 31 ms 7296 KB Output isn't correct
8 Incorrect 29 ms 7920 KB Output isn't correct
9 Incorrect 535 ms 51768 KB Output isn't correct
10 Incorrect 515 ms 55892 KB Output isn't correct