Submission #50083

#	Time	Username	Problem	Language	Result	Execution time	Memory
50083		chonka	Mate (COCI18_mate)	C++98	100 / 100	816 ms	29276 KiB

mate

#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 / 100