Cod sursa(job #1039975)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 23 noiembrie 2013 20:13:17
Problema Eval Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.64 kb
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

#define MAXL 2010
#define MAXP 120
#define MAXV 30

char S[100010], S1[100010];
int P[MAXP] = {1500000001, 1500000041,1500000043,1500000059,1500000077,1500000079,1500000101,1500000107,1500000113,1500000167,1500000233,1500000283,1500000301, 1500000373 ,1500000377 ,1500000409 ,1500000419 ,1500000427 ,1500000449 ,1500000473 ,1500000511 ,1500000527 ,1500000529 ,1500000563 ,1500000577 ,1500000587 ,1500000613 ,1500000617 ,1500000701 ,1500000707 ,1500000713 ,1500000721 ,1500000739 ,1500000743 ,1500000767 ,1500000773 ,1500000779 ,1500000787 ,1500000823 ,1500000829 ,1500000839 ,1500000851 ,1500000857 ,1500000871 ,1500000877 ,1500000893 ,1500000917 ,1500000973 ,1500001003 ,1500001033 ,1500001043 ,1500001049 ,1500001117 ,1500001213 ,1500001231 ,1500001241 ,1500001271 ,1500001291 ,1500001319 ,1500001333 ,1500001337 ,1500001343 ,1500001367 ,1500001369 ,1500001387 ,1500001397 ,1500001411 ,1500001421 ,1500001439 ,1500001453 ,1500001457 ,1500001507 ,1500001543 ,1500001549 ,1500001553 ,1500001577 ,1500001661 ,1500001673 ,1500001709 ,1500001733 ,1500001747 ,1500001751 ,1500001753 ,1500001777 ,1500001799 ,1500001801 ,1500001847 ,1500001859 ,1500001891 ,1500001907 ,1500001927 ,1500001939 ,1500001967 ,1500002057 ,1500002069 ,1500002071 ,1500002087 ,1500002099 ,1500002113 ,1500002117 ,1500002129 ,1500002143 ,1500002149 ,1500002197 ,1500002219 ,1500002233 ,1500002323 ,1500002381 ,1500002401 ,1500002419 ,1500002423 ,1500002503 ,1500002521 ,1500002527 ,1500002579 ,1500002591 ,1500002593 ,1500002639 ,1500002653 ,1500002657 };
int R[MAXP];
int Type[MAXV];
int Modul[MAXV];
int A[MAXL], B[MAXL], a[MAXL], b[MAXL], Ceva[MAXL];
int Variable[MAXV][MAXL];
int N, MOD, Poz;
int i, j, aux;

int Eval(void);
int Termen(void);
int Factor(void);

inline void Transform(int A[], int B)
{
    int i, t = B;
    for (i = 1; t; ++i, t /= 10)
        A[i] = t % 10;
    A[0] = i - 1;
}
inline int putere(int N, int K)
{
    int Ans = 1;
    for (int i = 0; (1LL<<i) <= K; ++i){
        if (K & (1<<i))
            Ans = (1LL * Ans * N) % MOD;
        N = (1LL * N * N) % MOD;
    }
    return Ans;
}

int Eval(void)
{
    int Rez = Termen();
    while (S[Poz] == '+' || S[Poz] == '-')
        if (S[Poz] == '+'){
            ++Poz;
            Rez = (1LL * Rez + Termen()) % MOD;
        }
        else{
            ++Poz;
            Rez = (MOD + 1LL * Rez - Termen()) % MOD;
        }
    return Rez;
}

int Termen(void)
{
    int Rez = Factor();
    while (S[Poz] == '*'){
        ++Poz;
        Rez = (1LL * Rez * Factor()) % MOD;
    }
    return Rez;
}

int Factor(void)
{
    int aux;
    switch (S[Poz]){
        case '(':
            ++Poz;
            aux = Eval();
            ++Poz;
            break;
        case '[':
            ++Poz;
            aux = Eval();
            aux = (1LL * aux * aux) % MOD;
            ++Poz;
            break;
        case '+':
            ++Poz;
            aux = Eval();
            break;
        case '-':
            ++Poz;
            aux = (MOD - Eval()) % MOD;
            break;
        default :
            if (Type[S[Poz] - 'a' + 1] == 0)
                aux = Modul[S[Poz] - 'a' + 1];
            else
                aux = MOD - Modul[S[Poz] - 'a' + 1];
            ++Poz;
            break;
    }
    return aux;
}

int Mod_mare(int A[])
{
    int Rest = 0;
    for (int i = A[0]; i >= 1; --i)
        Rest = (1LL * Rest * 10 + A[i]) % MOD;
    return Rest;
}

void Mul(int A[], int B)
{
    int i;
    long long t = 0;
    for (i = 1; i <= A[0] || t; ++i, t /= 10)
        A[i] = (t += 1LL * A[i] * B) % 10;
    A[0] = i - 1;
}

void Add(int A[], int B[])
{
    int i, t = 0;
    for (i = 1; i <= A[0] || i <= B[0] || t; ++i, t /= 10)
        A[i] = (t += A[i] + B[i]) % 10;
    A[0] = i - 1;
}

void Sub(int A[], int B[])
{
    int i, t = 0;
    for (i = 1; i <= A[0]; i++) {
        A[i] -= ((i <= B[0]) ? B[i] : 0) + t;
        A[i] += (t = A[i] < 0) * 10;
    }
    for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

int main()
{
    freopen("eval.in","r",stdin);
    freopen("eval.out","w",stdout);

    srand(10);

    scanf("%d\n", &N);
    for (i = 1; i <= N; ++i){
        gets(S1);
        if (S1[0] == '-'){
            Type[i] = 1;
            memcpy(S, S1+1, sizeof(S) - sizeof(int));
        }
        else
            memcpy(S, S1, sizeof(S));

        Variable[i][0] = strlen(S);
        for (j = 1; j <= Variable[i][0]; ++j)
            Variable[i][j] = S[Variable[i][0] - j] - '0';
    }
    gets(S);

    for (i = 0; i < MAXP; ++i){
        MOD = P[i];
        Poz = 0;
        for (j = 1; j <= N; ++j)
            Modul[j] = Mod_mare(Variable[j]);
        R[i] = Eval();
        R[i] = (1LL * R[i] + putere(10, 1000)) % MOD;
    }

    Transform(A, P[0]);
    Transform(a, R[0]);
    for (i = 1; i < MAXP; ++i){
        Transform(B, P[i]);
        Transform(b, R[i]);
        MOD = P[i];
        aux = Mod_mare(b) - Mod_mare(a);
        while (aux < 0) aux += MOD;
        aux = (1LL * aux * putere(Mod_mare(A), MOD - 2)) % MOD;

        if (aux != 0){
            memcpy(Ceva, A, sizeof(A));
            Mul(Ceva, aux);
        }
        else
            memset(Ceva, 0, sizeof(Ceva));

        Add(a, Ceva);
        Mul(A, P[i]);
    }

    memset(b, 0, sizeof(b));
    b[0] = 1001;
    b[1001] = 1;

    if (a[0] <= 1000){
        printf("-");
        Sub(b, a);
        memcpy(a, b, sizeof(b));
    }
    else
        Sub(a, b);

    for (i = a[0]; i >= 1; --i)
        printf("%d", a[i]);
    printf("\n");

    return 0;
}