oj.uz

Submission #239052

# Submission time Handle Problem Language Result Execution time Memory
239052 2020-06-14T08:50:46 Z topovik Mate (COCI18_mate) C++14
100 / 100
 1868 ms 15116 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define INF 1000000000
#define N (long)1e3*5+2

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e9+7;

int sf[26][N];

int otr[N][N];

int dp[26][26][N];

long long fact[N];
long long inv[N];
long long invfact[N];

inline long long C(ll n, ll k) {
	return fact[n] * invfact[k] % oo * invfact[n - k] % oo;
}

int main()
{
    fact[0] = invfact[0] = 1;
	for (ll i = 1; i < N; ++i) {
		inv[i] = (i == 1) ? 1 : oo - oo / i * inv[oo % i] % oo;
		fact[i] = fact[i - 1] * i % oo;
		invfact[i] = invfact[i - 1] * inv[i] % oo;
		assert(inv[i] * i % oo == 1);
	}
    string s;
    cin>>s;
    ll n=s.size();
    for (ll i=0; i<26; i++)
    {
        sf[i][n]=0;
        for (ll j=n-1; j>=0; j--) sf[i][j]=sf[i][j+1]+((s[j]-'a')==i);
    }
    for (ll i=0; i<n; i++)
    {
        ll mn[26];
        ll x=s[i]-'a';
        for (ll j=0; j<26; j++)
        {
            if ((char)(j+'a')!=s[i]) mn[j]=sf[j][i];
            else                     mn[j]=sf[j][i+1];
            for (ll c=0; c<=i; c++) dp[x][j][c+2]=(dp[x][j][c+2]+(C(i,c)*mn[j])%oo)%oo;
        }
    }
    ll q;
    cin>>q;
    while (q>0)
    {
        q--;
        ll x;
        char ch,ch1;
        cin>>x>>ch>>ch1;
        cout<<dp[ch-'a'][ch1-'a'][x]<<endl;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3448 KB Output is correct
2 Correct 51 ms 3072 KB Output is correct
3 Correct 61 ms 3328 KB Output is correct
4 Correct 94 ms 3200 KB Output is correct
5 Correct 329 ms 5496 KB Output is correct
6 Correct 369 ms 5508 KB Output is correct
7 Correct 287 ms 5312 KB Output is correct
8 Correct 250 ms 5112 KB Output is correct
9 Correct 1868 ms 14968 KB Output is correct
10 Correct 1763 ms 15116 KB Output is correct