Submission #239052

#	Time	Username	Problem	Language	Result	Execution time	Memory
239052		topovik	Mate (COCI18_mate)	C++14	100 / 100	1868 ms	15116 KiB

mate

#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 / 100