oj.uz

Submission #239287

# Submission time Handle Problem Language Result Execution time Memory
239287 2020-06-15T08:24:07 Z topovik Mate (COCI18_mate) C++14
100 / 100
 1559 ms 13688 KB 
#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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3072 KB Output is correct
2 Correct 41 ms 2944 KB Output is correct
3 Correct 49 ms 3072 KB Output is correct
4 Correct 82 ms 3072 KB Output is correct
5 Correct 270 ms 4860 KB Output is correct
6 Correct 305 ms 4852 KB Output is correct
7 Correct 228 ms 4756 KB Output is correct
8 Correct 202 ms 4600 KB Output is correct
9 Correct 1559 ms 13688 KB Output is correct
10 Correct 1552 ms 13688 KB Output is correct