oj.uz

Submission #239284

# Submission time Handle Problem Language Result Execution time Memory
239284 2020-06-15T08:19:10 Z topovik Mate (COCI18_mate) C++14
100 / 100
 1563 ms 17896 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()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    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 (register ll i=0; i<n; i++)
    {
        ll x=s[i]-'a';
        for (register ll j=0; j<26; j++)
        {
            const register int m=(char)(j+'a')==s[i]?sf[j][i+1]:sf[j][i];
            for (ll c=0; c<=i; c++) dp[x][j][c+2]=(dp[x][j][c+2]+(C(i,c)*m)%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 62 ms 3448 KB Output is correct
2 Correct 42 ms 3072 KB Output is correct
3 Correct 46 ms 3200 KB Output is correct
4 Correct 82 ms 3320 KB Output is correct
5 Correct 265 ms 5624 KB Output is correct
6 Correct 293 ms 5768 KB Output is correct
7 Correct 228 ms 5368 KB Output is correct
8 Correct 208 ms 5240 KB Output is correct
9 Correct 1547 ms 17896 KB Output is correct
10 Correct 1563 ms 17864 KB Output is correct