Cod sursa(job #936710)

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

using namespace std;

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

map<int, char> Map;
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;
}
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){
		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;
}