Cod sursa(job #979026)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 31 iulie 2013 10:23:17
Problema Eval Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.74 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;
}