Cod sursa(job #677172)

Utilizator crushackPopescu Silviu crushack Data 9 februarie 2012 21:40:17
Problema Eval Scor 20
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.42 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define LMax 1010
#define NMax 30
#define EMax 100010
using namespace std;

const char IN[]="eval.in",OUT[]="eval.out";
const int base = 10;
const int primes[]={1000000007,1000000009,1000000021,1000000033,1000000087,1000000093,1000000097,1000000103,1000000123,1000000181,1000000207,1000000223,1000000241,1000000271,1000000289,1000000297,1000000321,1000000349,1000000363,1000000403,1000000409,1000000411,1000000427,1000000433,1000000439,1000000447,1000000453,1000000459,1000000483,1000000513,1000000531,1000000579,1000000607,1000000613,1000000637,1000000663,1000000711,1000000753,1000000787,1000000801,1000000829,1000000861,1000000871,1000000891,1000000901,1000000919,1000000931,1000000933,1000000993,1000001011,1000001021,1000001053,1000001087,1000001099,1000001137,1000001161,1000001203,1000001213,1000001237,1000001263,1000001269,1000001273,1000001279,1000001311,1000001329,1000001333,1000001351,1000001371,1000001393,1000001413,1000001447,1000001449,1000001491,1000001501,1000001531,1000001537,1000001539,1000001581,1000001617,1000001621,1000001633,1000001647,1000001663,1000001677,1000001699,1000001759,1000001773,1000001789,1000001791,1000001801,1000001803,1000001819,1000001857,1000001887,1000001917,1000001927,1000001957,1000001963,1000001969,1000002043,1000002089,1000002103,1000002139,1000002149,1000002161,1000002173,1000002187,1000002193,1000002233,1000002239,1000002277,1000002307,1000002359,1000002361,1000002431,1000002449,1000002457,1000002499,1000002571,1000002581};
int mod;

int N;
int A[NMax][LMax] , nA[NMax] , M[EMax] , aux[EMax] , Rez[EMax];
char s[EMax],*r;

/// Big Nums Functions ------------------------------------

void add(int *a,int *b)
{
	int i,t=0;
	a[0]=max(a[0],b[0]);
	for (i=1;i<=a[0];++i)
	{
		a[i]=a[i]+b[i]+t;t=0;
		while (a[i]>=base) a[i]-=base,++t;
	}
	if (t)
		a[++a[0]]=t;
}

void diff(int *a,int *b)
{
	int i,t=0;
	for (i=1;i<=a[0];++i)
	{
		t= ( a[i]=a[i]-b[i]-t )<0 ? 1 : 0;
		a[i]+= t ? base : 0;
	}
	while (a[0]>1 && a[a[0]]==0) --a[0];
}

void inm(int *a,int b)
{
	int i,t=0;long long x;
	for (i=1;i<=a[0];++i)
	{
		x=1LL*a[i]*b+t;
		a[i]=x%base;
		t= x/base;
	}
	while (t)
		a[++a[0]]=t%10,t/=10;
}

void imp(int *a,int b)
{
	int i,r=0;long long x;
	for (i=a[0];i>0;--i)
	{
		x=(long long)r*base + a[i];
		a[i]= x/b;
		r=x%b;;
	}
	while (a[0]>1 && a[a[0]]==0) --a[0];
}

int modd(int *a,int b)
{
	int i,r=0;
	for (i=a[0];i>0;--i)
		r=((long long)r*base+a[i])%b;
	return r;
}

int cmp(int *a,int *b)
{
	int i;
	if ( a[0]>b[0]) return 1;
	if ( a[0]<b[0]) return -1;
	for (i=a[0];i>0 && a[i]==b[i];--i);
	if (a[i]>b[i]) return 1;
	if (a[i]<b[i]) return -1;
	return 0;
}

void read(int *x)
{
	int i;
	static char s[LMax];
	x[0]=0;
	fgets( s , LMax , stdin );
	for (i=0;s[i]!='\n';++i)
		x[++x[0]]=s[i]-'0';
	for (int a=1,b=x[0];a<b;++a,--b) swap(x[a],x[b]);
}

/// ---------------------------------------------------------

int eval(),eval_inm(),val();

int eval(){
	int ret=eval_inm();
	while (*r=='+' || *r=='-')
		if (*r=='+')
			++r,
			ret=(ret+eval_inm())%mod;
		else
			++r,
			ret=(ret+mod-eval_inm())%mod;
	return ret;
}

int eval_inm(){
	int ret=val();
	while (*r=='*')
		++r,
		ret=1LL*ret*val()%mod;
	return ret;
}

int val(){
	int ret;
	if (*r=='(')
		++r,
		ret=eval(),
		++r;
	else if (*r=='[')
		++r,
		ret=eval(),ret=1LL*ret*ret%mod,
		++r;
	else
	{
		int sgn=1;
		while (*r=='+' || *r=='-')
			sgn= (*r=='+' ? sgn : sgn),++r;
		ret=sgn*nA[*r-'a'],++r;
	}
	return ret;
}

int pow(int x,int p,int mod){
	int sol=1,i;
	for (i=0;(1<<i)<=p;++i)
	{
		if ( (1<<i)&p )
			sol= (1LL*sol*x)%mod;
		x=1LL*x*x%mod;
	}
	return sol;
}

void solve()
{
	int i,j,L=sizeof(primes)/sizeof(primes[0]);
	M[0]=M[1]=1;
	for (i=0;i<L;++i)
		inm(M,primes[i]);
	
	for (i=0;i<L;++i)
	{
		memcpy(aux,M,sizeof(M));
		imp(aux,primes[i]);
		
		int mp=modd(aux,primes[i]);
		mp=pow(mp,primes[i]-2,primes[i]);
		
		mod=primes[i];r=s;
		for (j=0;j<N;++j) nA[j]=modd(A[j],mod);
		int a=eval();
		
		inm(aux,a);inm(aux,mp);
		
		add(Rez,aux);
		while (cmp(Rez,M)>=0) diff(Rez,M);
	}
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d\n",&N);
	for (i=0;i<N;++i) read(A[i]);
	fgets(s,EMax,stdin);
	
	solve();
	
	freopen(OUT,"w",stdout);
	for (i=Rez[0];i>0;--i)
		printf("%d",Rez[i]);
	printf("\n");
	fclose(stdout);
	
	return 0;
}