Cod sursa(job #1978417)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 7 mai 2017 17:50:35
Problema Eval Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.23 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "eval.in"  );
ofstream out( "eval.out" );

const int NMAX = 27;
const int DMAX = 321;
const int LMAX = 1005;
const int SMAX = 100005;
const int BASE = 10000;
const int NBASE = 4;

char axs[LMAX], str[SMAX];

int axn[DMAX], ans[DMAX], aux[DMAX];
int num[NMAX][DMAX], sign[NMAX], val[NMAX];

vector<int> axp{ 1999997017, 1999997089, 1999997107, 1999997117, 1999997141, 1999997159, 1999997189, 1999997203, 1999997213, 1999997239, 1999997273, 1999997341, 1999997359, 1999997393, 1999997411, 1999997413, 1999997429, 1999997459, 1999997491, 1999997537, 1999997543, 1999997563, 1999997569, 1999997579, 1999997599, 1999997603, 1999997611, 1999997621, 1999997633, 1999997641, 1999997663, 1999997689, 1999997711, 1999997719, 1999997773, 1999997777, 1999997807, 1999997849, 1999997873, 1999997887, 1999997903, 1999997941, 1999997957, 1999997971, 1999997981, 1999998029, 1999998047, 1999998103, 1999998149, 1999998181, 1999998193, 1999998239, 1999998313, 1999998347, 1999998359, 1999998383, 1999998389, 1999998401, 1999998421, 1999998443, 1999998457, 1999998479, 1999998493, 1999998527, 1999998551, 1999998617, 1999998631, 1999998641, 1999998701, 1999998719, 1999998733, 1999998743, 1999998761, 1999998769, 1999998773, 1999998797, 1999998799, 1999998809, 1999998823, 1999998827, 1999998857, 1999998893, 1999998899, 1999998907, 1999998941, 1999998947, 1999998961, 1999999003, 1999999013, 1999999049, 1999999061, 1999999081, 1999999087, 1999999093, 1999999097, 1999999117, 1999999121, 1999999151, 1999999171, 1999999207, 1999999219, 1999999271, 1999999321, 1999999373, 1999999423, 1999999439, 1999999499, 1999999553, 1999999559, 1999999571, 1999999609, 1999999613, 1999999621, 1999999643, 1999999649, 1999999657, 1999999747, 1999999763, 1999999777, 1999999811 };

inline int mod( int a[DMAX], int b ) {
    int i; long long t = 0;
    
    for( i = a[0]; i >= 1; i -- )
        t = ( t * BASE + a[i] ) % b;
    
    return (int) t;
}

inline void add( int a[DMAX], int b[DMAX] ) {
    int i, t = 0;
    
    for( i = 1; i <= a[0] || i <= b[0]; i ++, t /= BASE )
        a[i] = ( t += a[i] + b[i] ) % BASE;
    a[0] = i - 1;
    
    return;
}

inline void mul( int a[DMAX], int b ) {
    int i; long long t = 0;
    
    if( b == 0 )
        memset( a, 0, ( a[0] + 1 ) << 2 );
    else {
        for( i = 1; i <= a[0] || t; i ++, t /= BASE )
            a[i] = ( t += 1LL * a[i] * b ) % BASE;
        a[0] = i - 1;
    }
    
    return;
}

inline void sub( int a[DMAX], int b[DMAX] ) {
    int i, t = 0;
    
    for( i = 1; i <= a[0]; i ++ ) {
        a[i] -= b[i] + t;
        a[i] += ( t = a[i] < 0 ) * BASE;
    }
    
    while( a[0] > 0 && a[a[0]] == 0 )
        a[0] --;
    
    return;
}

inline int cmp( int a[DMAX], int b[DMAX] ) {
    if( a[0] != b[0] )
        return ( a[0] < b[0] ) ? -1 : 1;
    
    for( int i = a[0]; i >= 1; i -- ) {
        if( a[i] != b[i] )
            return ( a[i] < b[i] ) ? -1 : 1;
    }
    
    return 0;
}

int expr( int &p, int r );
int term( int &p, int r );
int fact( int &p, int r );
int numb( int &p, int r );

int expr( int &p, int r ) {
    int nr = term( p, r );
    
    while( str[p] == '+' || str[p] == '-' ) {
        if( str[p] == '+' )
            nr = ( 0LL + nr + term( ++ p, r ) + r ) % r;
        else
            nr = ( 0LL + nr - term( ++ p, r ) + r ) % r;
    }
    
    return nr;
}

int term( int &p, int r ) {
    int nr = fact( p, r );
    
    while( str[p] == '*' )
        nr = ( 1LL * nr * fact( ++ p, r ) ) % r;
    
    return nr;
}

int fact( int &p, int r ) {
    int nr = 0;
    
    if( str[p] != '+' && str[p] != '-' ) {
        if( str[p] == '(' ) {
            nr = expr( ++ p, r );
            p ++;
        }
        else
            nr = numb( p, r );
    }
    else {
        if( str[p] == '+' )
            nr = expr( ++ p, r );
        else
            nr = ( 0LL + r - expr( ++ p, r ) ) % r;
    }
    
    return nr;
}

int numb( int &p, int r ) {
    int nr = 0;
    
    if( str[p] == '[' ) {
        nr = expr( ++ p, r ); p ++;
        nr = ( 1LL * nr * nr ) % r;
    }
    else {
        nr = val[str[p] - 'a' + 1];
        p ++;
    }
    
    return nr;
}

int runexp( int n, int r ) {
    for( int i = 1; i <= n; i ++ ) {
        val[i] = mod( num[i], r );
        
        if( sign[i] == -1 )
            val[i] = r - val[i];
    }
    
    int p = 1;
    return expr( p, r );
}

int lgput( int x, int y, int r ) {
    if( y == 0 )
        return 1;
    
    int z = lgput( x, y / 2, r );
    z = ( 1LL * z * z ) % r;
    
    if( y % 2 == 1 )
        z = ( 1LL * z * x ) % r;
    
    return z;
}

inline void solve( int n ) {
    memset( axn, 0, sizeof( axn ) );
    memset( ans, 0, sizeof( ans ) );
    
    axn[0] = axn[1] = ans[0] = ans[1] = 1;
    
    int nr = 0;
    for( int prm : axp ) {
        int rst = runexp( n, prm );
        
        nr ++;
        if( nr == 1 ) {
            mul( axn, prm );
            mul( ans, rst );
        }
        else {
            int aux1 = ( 0LL + rst - mod( ans, prm ) + prm ) % prm;
            int aux2 = lgput( mod( axn, prm ), prm - 2, prm );
            
            memcpy( aux, axn, ( axn[0] + 1 ) << 2 ); mul( axn, prm );
            mul( aux, ( 1LL * aux1 * aux2 ) % prm ); add( ans, aux );
        }
    }
    
    return;
}

int main( void ) {
    
    int n;
    in >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        in >> ( axs + 1 );
        int l = (int) strlen( axs + 1 );
        
        if( axs[1] == '-' )
            sign[i] = -1;
        else
            sign[i] = +1;
        
        for( int j = l; j >= 1 + ( sign[i] == -1 ); j -= NBASE ) {
            num[i][0] ++;
            
            for( int k = max( j - NBASE + 1, 1 + ( sign[i] == -1 ) ); k <= j; k ++ )
                num[i][num[i][0]] = num[i][num[i][0]] * 10 + ( axs[k] - '0' );
        }
    }
    
    in >> ( str + 1 );
    solve( n );

    memset( aux, 0, sizeof( aux ) );
    aux[0] = DMAX - 70; aux[DMAX - 70] = 1;

    if( cmp( ans, aux ) > 0 ) {
        out << '-';
        
        for( int i = 1; i <= n; i ++ )
            sign[i] *= -1;
        solve( n );
    }

    out << ans[ans[0]];
    for( int i = ans[0] - 1; i >= 1; i -- ) {
        for( int aux = BASE / 10; aux > ans[i] && aux > 1; aux /= 10 )
            out << 0;
        out << ans[i];
    }
    
    return 0;
}