Cod sursa(job #936709)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 8 aprilie 2013 14:23:33
Problema Eval Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.91 kb
#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>

using namespace std;

#define MAXL 2010
#define MAXP 130
#define MAXV 30

map<int, char> Map;
char S[100010], S1[100010];
int P[MAXP], 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; (1<<i) <= K; ++i){
		if (K & (1<<i))
			Ans = (1LL * Ans * N) % MOD;
		N = (1LL * N * N) % MOD;
	}
	return Ans;
}
inline void Verif(int N)
{
	if (Map[N] >= 1) return;
	if (N % 2 == 0) {
		Map[N] = 2;
		return;
	}
	for (int i = 3; i * i <= N; i += 2)
		if (N % i == 0){
			Map[N] = 2;
			return;
		}
	Map[N] = 1;
}

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){
		/*do{//misto ideea :D
			P[i] = 1000000000 + (rand() % 1000000000);
			Verif(P[i]);
		}while (Map[P[i]] == 2);*/
		P[i] = 2;
		Map[P[i]] = 2;
		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;
}