Submission #239287

#	Time	Username	Problem	Language	Result	Execution time	Memory
239287		topovik	Mate (COCI18_mate)	C++14	100 / 100	1559 ms	13688 KiB

mate

#include <bits/stdc++.h>

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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)
    {
        q--;
        ll x;
        char ch,ch1;
        cin>>x>>ch>>ch1;
        cout<<dp[ch-'a'][ch1-'a'][x]<<endl;
    }
}

Compilation message (stderr)

mate.cpp:3:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

• Subtask 1: 100 / 100