Cod sursa(job #2007574)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 3 august 2017 12:45:48
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include<fstream>
#include<map>
#include<cstring>
#include<cstdlib>
#define MAX_LEN 1500
#define ll long long
using namespace std;
ifstream f("eval.in"); ofstream g("eval.out");
int N,p,P[120],R[120],V[26],MOD,p1[MAX_LEN],r1[MAX_LEN],p2[MAX_LEN],r2[MAX_LEN];
char var[26][MAX_LEN], expr[100005];
map <int, bool> H;
inline int is_prime(int n)
{   if(!(n%2)) return 0;
    for(int i=3; i*i<=n; i+=2)
        if(!(n%i)) return 0;
    return 1;
}
int mod_var(char str[], int mod)
{   int i,ret=0;
    for(i=str[0]=='-'; str[i]; i++)
        ret=((ll) ret*10 + str[i]-'0') % mod;
    return str[0] == '-' ? (mod-ret)%mod : ret;
}
inline void add(int &a, int b) {a=((ll)a+b)%MOD;}
inline void mul(int &a, int b) {a=((ll)a*b)%MOD;}
int eval(),term(),factor();
int eval()
{   int ret = term();
    while(expr[p]=='+'||expr[p]=='-')
        if(expr[p]=='+') {p++; add(ret,term());}
            else {p++;add(ret,MOD-term());}
    return ret;
}
int term()
{   int ret=factor();
    while(expr[p]=='*') {p++; mul(ret,factor());}
    return ret;
}
int factor()
{   int ret;
    if(expr[p]=='(') {p++; ret=eval(); p++;}
    else if(expr[p]=='[') {p++; ret=eval(); mul(ret,ret); p++;}
            else if(expr[p]=='-') {p++; ret = -eval(); add(ret, MOD);}
                    else if(expr[p]=='+') {p++; ret=eval();}
                            else
    if(expr[p]>='a'&&expr[p]<='z') {ret=V[expr[p]-'a']; p++;}
    return ret;
}
inline void init(int a[], int b)
{   memset(a,0,MAX_LEN*sizeof(int));
    for(;b;b/=10) a[++a[0]]=b%10;
}
int modM(int a[], int b)
{   int i,ret=0;
    for(i=a[0];i;i--) ret=((ll)ret*10+a[i])%b;
    return ret;
}
void addM(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 scadM(int a[], int b[])
{   int i,t=0;
    for(i=1;i<=a[0];i++)
    {   a[i]-=b[i]+t;
        a[i]+=(t=a[i]<0)*10;
    }
    for(;a[0] && !a[a[0]]; a[0]--);
}
void prodM(int a[], int b)
{   int i; ll t=0;
    for(i=1;i<=a[0] || t; i++,t/=10)
        a[i]=(t+=(ll)a[i]*b)%10;
    a[0]=i-1;
}
void prodM(int a[], int b[])
{   int i,j,c[MAX_LEN]; ll t;
    memset(c, 0, sizeof(c));
    for(i=1; i<=a[0]; i++)
    {   for(j=1,t=0; j<= b[0]||t; j++, t/=10)
            c[i+j-1]=(t+=c[i+j-1]+(ll)a[i]*b[j])%10;
        if(c[0]<i+j-2) c[0]=i+j-2;
    }
    memcpy(a,c,sizeof(c));
}
int pow(int a, int b, int mod)
{   int t;
    if(b==0) return 1;
    t=pow(a,b>>1,mod);
    t=((ll)t*t)%mod;
    if(b&1) t=((ll)t*a)%mod;
    return t;
}
int main(void)
{   int i,j,k,n,a,b,t[MAX_LEN];
    f>>N;
    for(i=0;i<N;i++) f>>var[i];
    f>>expr;
    for(i=0;i<120;i++)
    {   do n=1000000000+(rand()>>1); while(H[n] || !is_prime(n));
        H[n]=true; P[i]=n;
        for(j=0; j<N; j++) V[j]=mod_var(var[j],P[i]);
        p=0; MOD=P[i];
        R[i]=eval();
        add(R[i],pow(10,1000,MOD));
    }
    init(p1,P[0]); init(r1,R[0]);
    for(i=1; i<120; i++)
    {   init(p2,P[i]); init(r2,R[i]);
        a=modM(r2,P[i])-modM(r1,P[i]);
        while(a<0) a+=P[i];
        b=pow(modM(p1,P[i]),P[i]-2,P[i]);
        k=((ll)a*b)%P[i];
        if (k)
        {   memcpy(t,p1,sizeof(p1));
            prodM(t,k); addM(r1,t);
        }
        prodM(p1,p2);
    }
    memset(t,0,sizeof(t));
    t[0]=1001; t[1001]=1;
    if(r1[0]<1001)
    {   scadM(t,r1);
        memcpy(r1,t,sizeof(t));
        g<<"-";
    } else scadM(r1,t);
    for(i=r1[0];i;i--) g<<r1[i];
    g<<'\n'; g.close(); return 0;
}