Submission #89886

#	Time	Username	Problem	Language	Result	Execution time	Memory
89886		vex	Mate (COCI18_mate)	C++14	100 / 100	1810 ms	51480 KiB

mate

#include <bits/stdc++.h>
#define maxn 2005
#define MOD 1000000007
using namespace std;

int n,q;
string s;
long long bc[maxn][maxn];
long long poj[maxn][26];
long long sol[maxn][26][26];
long long f[maxn];
long long invf[maxn];

long long ste(long long x,long long y)
{
    if(y==0)return 1LL;
    if(y%2==0)
    {
        long long res=ste(x,y/2);
        return (res*res)%MOD;
    }
    return (x*ste(x,y-1))%MOD;
}
long long inv(long long x){return ste(x,MOD-2);}
void resi()
{
    f[0]=1LL;
    for(int i=1;i<=n;i++)f[i]=(f[i-1]*i)%MOD;
    for(int i=0;i<=n;i++)invf[i]=inv(f[i]);

    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
        {
            bc[i][j]=(f[i]*invf[j])%MOD;
            bc[i][j]=(bc[i][j]*invf[i-j])%MOD;
        }

    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<26;j++)poj[i][j]=poj[i+1][j];
        poj[i][s[i]-'a']++;
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=25;j++)
            for(int k=2;k<=min(n,i+2);k++)
            {
                sol[k][s[i]-'a'][j]+=(bc[i][k-2]*poj[i+1][j])%MOD;
                sol[k][s[i]-'a'][j]%=MOD;
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>s>>q;
    n=s.size();
    resi();

    /*for(int i=0;i<10;i++)cout<<f[i]<<","<<invf[i]<<"  ";cout<<endl;
    for(int i=0;i<=n;i++)
    {
        cout<<i<<": ";
        for(int j=0;j<=i;j++)cout<<j<<","<<bc[i][j]<<" ";
        cout<<endl;
    }*/

    for(int i=0;i<q;i++)
    {
        string ww;
        int len;
        cin>>len>>ww;
        int a=ww[0]-'a';
        int b=ww[1]-'a';
        cout<<sol[len][a][b]<<endl;
    }
    return 0;
}

• Subtask 1: 100 / 100