oj.uz

Submission #89886

# Submission time Handle Problem Language Result Execution time Memory
89886 2018-12-18T18:58:35 Z vex Mate (COCI18_mate) C++14
100 / 100
 1810 ms 51480 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1272 KB Output is correct
2 Correct 32 ms 1392 KB Output is correct
3 Correct 42 ms 1444 KB Output is correct
4 Correct 69 ms 1768 KB Output is correct
5 Correct 243 ms 5124 KB Output is correct
6 Correct 255 ms 6128 KB Output is correct
7 Correct 189 ms 6800 KB Output is correct
8 Correct 174 ms 7296 KB Output is correct
9 Correct 1581 ms 47236 KB Output is correct
10 Correct 1810 ms 51480 KB Output is correct