Cod sursa(job #1722843)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 29 iunie 2016 01:59:19
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.14 kb
#include<cstdio>
#include<cstring>
#define MAXN 30
#define MAXDIGITS 1010
#define MAXL 100010
#define PRIMES 109
using namespace std;
char variable[MAXN][MAXDIGITS];
char expression[MAXL];
int value[MAXN],result[PRIMES+10];
int p1[MAXDIGITS],p2[MAXDIGITS],r1[MAXDIGITS],r2[MAXDIGITS],temp[MAXDIGITS];
int prime[PRIMES]={0,2147483647,2147483629,2147483587,2147483579,2147483563,2147483549,2147483543,2147483497,2147483489,2147483477,2147483423,2147483399,2147483353,2147483323,2147483269,2147483249,2147483237,2147483179,2147483171,2147483137,2147483123,2147483077,2147483069,2147483059,2147483053,2147483033,2147483029,2147482951,2147482949,2147482943,2147482937,2147482921,2147482877,2147482873,2147482867,2147482859,2147482819,2147482817,2147482811,2147482801,2147482763,2147482739,2147482697,2147482693,2147482681,2147482663,2147482661,2147482621,2147482591,2147482583,2147482577,2147482507,2147482501,2147482481,2147482417,2147482409,2147482367,2147482361,2147482349,2147482343,2147482327,2147482291,2147482273,2147482237,2147482231,2147482223,2147482121,2147482093,2147482091,2147482081,2147482063,2147482021,2147481997,2147481967,2147481949,2147481937,2147481907,2147481901,2147481899,2147481893,2147481883,2147481863,2147481827,2147481811,2147481797,2147481793,2147481673,2147481629,2147481571,2147481563,2147481529,2147481509,2147481499,2147481491,2147481487,2147481373,2147481367,2147481359,2147481353,2147481337,2147481317,2147481311,2147481283,2147481269,2147481263,2147481247,2147481209,2147481199};
int Power(int base,int power,int mod){
    int answer=1;
    while(power>0){
        if(power%2==1)
            answer=((long long)answer*base)%mod;
        base=((long long)base*base)%mod;
        power/=2;
    }
    return answer;
}
int Modulo(char s[MAXDIGITS],int mod){
    int i,answer=0;
    for(i=s[0]=='-';s[i]!=0;i++)
        answer=((long long)answer*10+s[i]-'0')%mod;
    if(s[0]=='-')
        return (mod-answer)%mod;
    return answer;
}
int Evaluate(),Term(),Factor(),pointer,MOD;
int Evaluate(){
    int answer=Term();
    while(expression[pointer]=='+'||expression[pointer]=='-')
        if(expression[pointer]=='+'){
            pointer++;
            answer=((long long)answer+Term())%MOD;
        }
        else{
            pointer++;
            answer=((long long)answer+MOD-Term())%MOD;
        }
    return answer;
}
int Term(){
    int answer=Factor();
    while(expression[pointer]=='*'){
        pointer++;
        answer=((long long)answer*Factor())%MOD;
    }
    return answer;
}
int Factor(){
    int answer;
    if(expression[pointer]=='('){
        pointer++;
        answer=Evaluate();
        pointer++;
    }
    else
        if(expression[pointer]=='['){
            pointer++;
            answer=Evaluate();
            answer=((long long)answer*answer)%MOD;
            pointer++;
        }
        else
            if(expression[pointer]=='-'){
                pointer++;
                answer=-Evaluate();
                answer=((long long)answer+MOD)%MOD;
            }
            else
                if(expression[pointer]=='+'){
                    pointer++;
                    answer=Evaluate();
                }
                else
                    if(expression[pointer]>='a'&&expression[pointer]<='z'){
                        answer=value[expression[pointer]-'a'+1];
                        pointer++;
                    }
    return answer;
}
void Initialize(int v[MAXDIGITS],int k){
    memset(v,0,sizeof(v));
    while(k>0){
        v[0]++;
        v[v[0]]=k%10;
        k/=10;
    }
}
int Modulo1(int v[MAXDIGITS],int k){
    int i,answer=0;
    for(i=v[0];i>=1;i--)
        answer=((long long)answer*10+v[i])%k;
    return answer;
}
void Multiply1(int v[MAXDIGITS],int k){
    int i;
    long long c=0;
    for(i=1;i<=v[0];i++){
        v[i]=(c+=(long long)v[i]*k)%10;
        c/=10;
    }
    while(c>0){
        v[0]++;
        v[v[0]]=c%10;
        c/=10;
    }
}
void Add1(int a[MAXDIGITS],int b[MAXDIGITS]){
    int i,c=0;
    for(i=1;i<=a[0]||i<=b[0];i++){
        a[i]=a[i]+b[i]+c;
        c=a[i]/10;
        a[i]%=10;
    }
    if(b[0]>a[0])
        a[0]=b[0];
    while(c>0){
        a[0]++;
        a[a[0]]=c%10;
        c/=10;
    }
}
void Multiply2(int a[MAXDIGITS],int b[MAXDIGITS]){
    int i,j,c[MAXDIGITS];
    long long k=0;
    memset(c,0,sizeof(c));
    for(i=1;i<=a[0];i++){
        for(j=1,k=0;j<=b[0]||k>0;j++,k/=10)
            c[i+j-1]=(k+=c[i+j-1]+(long long)a[i]*b[j])%10;
        if(c[0]<i+j-2)
            c[0]=i+j-2;
    }
    memcpy(a,c,sizeof(c));
}
void Subtract1(int a[MAXDIGITS],int b[MAXDIGITS]){
    int i,k=0;
    for(i=1;i<=a[0];i++){
        a[i]=a[i]-b[i]-k;
        if(a[i]<0){
            k=1;
            a[i]+=10;
        }
        else
            k=0;
    }
    while(a[0]>0&&a[a[0]]==0)
        a[0]--;
}
int main(){
    freopen("eval.in","r",stdin);
    freopen("eval.out","w",stdout);
    int n,i,j,x,y,z;
    scanf("%d\n",&n);
    for(i=1;i<=n;i++)
        scanf("%s",variable[i]);
    scanf("%s",expression);
    for(i=1;i<PRIMES;i++){
        for(j=1;j<=n;j++)
            value[j]=Modulo(variable[j],prime[i]);
        pointer=0;
        MOD=prime[i];
        result[i]=Evaluate();
        result[i]=((long long)result[i]+Power(10,1000,prime[i]))%prime[i];
    }
    Initialize(p1,prime[1]);
    Initialize(r1,result[1]);
    for(i=2;i<PRIMES;i++){
        Initialize(p2,prime[i]);
        Initialize(r2,result[i]);
        x=Modulo1(r2,prime[i])-Modulo1(r1,prime[i]);
        while(x<0)
            x+=prime[i];
        y=Power(Modulo1(p1,prime[i]),prime[i]-2,prime[i]);
        z=((long long)x*y)%prime[i];
        if(z!=0){
            memcpy(temp,p1,sizeof(p1));
            Multiply1(temp,z);
            Add1(r1,temp);
        }
        Multiply2(p1,p2);
    }
    memset(temp,0,sizeof(temp));
    temp[0]=1001;
    temp[1001]=1;
    if(r1[0]<1001){
        Subtract1(temp,r1);
        memcpy(r1,temp,sizeof(temp));
        printf("-");
    }
    else
        Subtract1(r1,temp);
    for(i=r1[0];i>=1;i--)
        printf("%d",r1[i]);
    return 0;
}