oj.uz

Submission #50083

# Submission time Handle Problem Language Result Execution time Memory
50083 2018-06-07T13:36:52 Z chonka Mate (COCI18_mate) C++
100 / 100
 816 ms 29276 KB 
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std ;

#define MAXN 2007
#define MOD 1000000007

int n ;
string a ;
int q ;

long long fac[ MAXN ] ;
long long invfac[ MAXN ] ;
int br[ MAXN ] ;
long long ans[ MAXN ][ 27 ][ 27 ] ;

long long fastpow ( long long x , long long st ) {
    long long ret = 1 ;
    while ( st != 0 ) {
        if ( ( st % 2 ) == 0 ) {
            st /= 2 ;
            x = ( x * x ) % MOD ;
        }
        else {
            st -- ;
            ret = ( ret * x ) % MOD ;
        }
    }
    return ret ;
}

void input ( ) {
    cin >> a ;
    n = a.size ( ) ;
    fac[ 0 ] = 1 ;
    invfac[ 0 ] = fastpow ( fac[ 0 ] , MOD - 2 ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        fac[ i ] = ( fac[ i - 1 ] * i ) % MOD ;
        invfac[ i ] = fastpow ( fac[ i ] , MOD - 2 ) ;
    }
}

void solve ( ) {
    int i , j , t ;
    cin >> q ;
    for ( i = 2 ; i <= n ; i ++ ) {
        for ( j = 0 ; j < 26 ; j ++ ) {
            br[ j ] = 0 ;
        }
        for ( j = n ; j >= i - 1 ; j -- ) {
            int id = ( a[ j - 1 ] - 'a' ) ;
            for ( t = 0 ; t < 26 ; t ++ ) {
                long long cur = br[ t ] ;
                cur = ( cur * fac[ j - 1 ] ) % MOD ;
                cur = ( cur * invfac[ i - 2 ] ) % MOD ;
                cur = ( cur * invfac[ j - i + 1 ] ) % MOD ;
                ans[ i ][ id ][ t ] = ( ans[ i ][ id ][ t ] + cur ) % MOD ;
            }
            br[ id ] ++ ;
        }
    }
    while ( q != 0 ) {
        q -- ;
        int len ;
        string aux ;
        cin >> len >> aux ;
        int x = ( aux[ 0 ] - 'a' ) ;
        int y = ( aux[ 1 ] - 'a' ) ;
        cout << ans[ len ][ x ][ y ] << "\n" ;
    }
}

int main ( ) {
    ios_base::sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 888 KB Output is correct
2 Correct 7 ms 1196 KB Output is correct
3 Correct 8 ms 1380 KB Output is correct
4 Correct 11 ms 1580 KB Output is correct
5 Correct 43 ms 4064 KB Output is correct
6 Correct 52 ms 5196 KB Output is correct
7 Correct 40 ms 5872 KB Output is correct
8 Correct 35 ms 6332 KB Output is correct
9 Correct 770 ms 25020 KB Output is correct
10 Correct 816 ms 29276 KB Output is correct