Cod sursa(job #970447)

Utilizator geniucosOncescu Costin geniucos Data 6 iulie 2013 20:28:10
Problema Eval Scor 20
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.34 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int semn,pp,po,i,j,n,nr,Mod,ii,p[200],r[200],v[30][200];
char cif[2013],sir[100013];
///////////////////////////////////////////////////declaratii pentru TCR
void swap(int &x,int &y)
{
    int aux=x;
    x=y;
    y=aux;
}
struct str
{
    int l;
    int v[1009];
};
str acr,Rez,a1,b1,QQ;
str atr(int val)
{
    while(val)
    {
        acr.l++;
        acr.v[acr.l]=val%10;
        val/=10;
    }
    return acr;
}
str orint(str a,int k)
{
    int i;
    long long aux,t=0;
    if(k==0)
    {
        acr.l=1;
        acr.v[1]=0;
        return acr;
    }
    for(i=1;i<=a.l;i++)
    {
        aux=1LL*a.v[i]*k;
        aux+=t;
        t=aux/10;
        a.v[i]=aux%10;
    }
    while(t)
    {
        a.l++;
        a.v[a.l]=t%10;
        t/=10;
    }
    return a;
}
str suma(str a,str b)
{
    int i,t=0;
    for(i=a.l+1;i<=b.l;i++)
        a.v[i]=0;
    for(i=b.l+1;i<=a.l;i++)
        b.v[i]=0;
    acr.l=b.l;
    if(a.l>b.l) acr.l=a.l;
    for(i=1;i<=acr.l;i++)
    {
        acr.v[i]=(a.v[i]+b.v[i]+t)%10;
        t=(a.v[i]+b.v[i]+t)/10;
    }
    if(t){acr.l++;acr.v[acr.l]=t;}
    while(acr.v[acr.l]==0&&acr.l) acr.l--;
    return acr;
}
int modulo(str a,int k)
{
    int p=0;
    for(i=a.l;i>=1;i--)
        p=(1LL*p*10+a.v[i])%k;
    return p;
}
int pow(int a,int b,int mod)
{
    int i,p=1;
    for(i=0;(1LL<<i)<=b;i++)
    {
        if(b&(1LL<<i)) p=(1LL*p*a)%mod;
        a=(1LL*a*a)%mod;
    }
    return p;
}
bool cmp(int p1,int p2)
{
    return r[p1]>r[p2];
}
str recon(int n)
{
    int i,ii,a2,b2,b1mb2,q,Q,ind[250];
    for(i=1;i<=n;i++) ind[i]=i;
    sort(ind+1,ind+n+1,cmp);
    a1=atr(r[ind[1]]);
    b1=atr(p[ind[1]]);
    for(ii=2;ii<=n;ii++)
    {
        a2=r[ind[ii]];
        b2=p[ind[ii]];
        b1mb2=modulo(b1,b2);
        q=pow(b1mb2,b2-2,b2);
        ////////////////////am a1=a1+b1*q
        Q=((a2%b2-modulo(a1,b2))%b2+b2)%b2;
        Q=(1LL*Q*q)%b2;
        QQ=orint(b1,Q);
        a1=suma(a1,QQ);
        ///////////////////
        b1=orint(b1,b2);
    }
    return a1;
}
void afis(str a)
{
    int i;
    for(i=a.l;i>=1;i--)
        printf("%d",a.v[i]);
    printf("\n");
}
//////////////////////////////////////////////////////////Evaluare expresiei
int suma();
int termen();
int factor();
int suma()
{
    int smn,sum=termen();
    while(sir[i]=='+'||sir[i]=='-')
    {
        smn=0;
        while(sir[i]=='+'||sir[i]=='-')
        {
            if(sir[i]=='-') smn^=1;
            i++;
        }
        if(smn==0) sum+=termen();
        else sum-=termen();
        if(sum<0) sum+=Mod;
        if(sum>=Mod) sum-=Mod;
    }
    return sum;
}
int termen()
{
    int prod=factor();
    while(sir[i]=='*')
    {
        i++;
        prod=(1LL*prod*factor())%Mod;
    }
    return prod;
}
int factor()
{
    int smn,fac=0;
    if(sir[i]=='(')
    {
        i++;
        fac=suma();
        i++;
        return fac;
    }
    if(sir[i]=='[')
    {
        i++;
        fac=suma();
        i++;
        return (1LL*fac*fac)%Mod;
    }
    smn=0;
    while(sir[i]=='-'||sir[i]=='+')
    {
        if(sir[i]=='-') smn^=1;
        i++;
    }
    if(smn==0) smn=1;
    else smn=-1;
    fac=v[sir[i]-'a'][ii];
    i++;
    fac*=smn;
    if(fac<0) fac+=Mod;
    return fac;
}
/////////////////////////////////////////////////////////
int main()
{
freopen("eval.in","r",stdin);
freopen("eval.out","w",stdout);
scanf("%d\n",&n);
///////////////////////imi fac un vector p de lungime nr cu numere prime cu p[1]*p[2]*...*p[nr]>=2*10^1000
for(i=1500000000;i<=2000000000;i++)
{
    for(j=2;j*j<=i;j++)
        if(i%j==0) break;
    if(j*j>i)
    {
        nr++;
        p[nr]=i;
        if(nr==120) break;
    }
}
///////////////////////
for(i=1;i<=n;i++)
{
    gets(cif+1);
    semn=pp=1;
    if(cif[1]=='-')
    {
        semn=-1;
        pp=2;
    }
    for(j=1;j<=nr;j++)
    {
        po=pp;
        while(cif[po]>='0'&&cif[po]<='9')
        {
            v[i-1][j]=(1LL*v[i-1][j]*10+cif[po]-48)%p[j];
            po++;
        }
        v[i-1][j]*=semn;
        if(v[i-1][j]<0) v[i-1][j]+=p[j];
    }
}
gets(sir+1);
for(ii=1;ii<=nr;ii++)
{
    Mod=p[ii];
    i=1;
    r[ii]=suma();
}
Rez=recon(nr);
afis(Rez);
return 0;
}