Cod sursa(job #2640431)

Utilizator bogdi1bogdan bancuta bogdi1 Data 6 august 2020 13:50:14
Problema Eval Scor 90
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 7.05 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int nrprime = 120;
int valmod[120];
int val[120][10005];
char s[100005];
int rest[120];
int prime1[10005];
int prime2[10005];
int rest1[10005];
int rest2[10005];
int aux[10005];
bool eneg[120];
int aux1[10005];
int ind,mod;
const int kPrimes[] = {1999997017, 1999997089, 1999997107, 1999997117, 1999997141, 1999997159, 1999997189, 1999997203, 1999997213, 1999997239, 1999997273, 1999997341, 1999997359, 1999997393, 1999997411, 1999997413, 1999997429, 1999997459, 1999997491, 1999997537, 1999997543, 1999997563, 1999997569, 1999997579, 1999997599, 1999997603, 1999997611, 1999997621, 1999997633, 1999997641, 1999997663, 1999997689, 1999997711, 1999997719, 1999997773, 1999997777, 1999997807, 1999997849, 1999997873, 1999997887, 1999997903, 1999997941, 1999997957, 1999997971, 1999997981, 1999998029, 1999998047, 1999998103, 1999998149, 1999998181, 1999998193, 1999998239, 1999998313, 1999998347, 1999998359, 1999998383, 1999998389, 1999998401, 1999998421, 1999998443, 1999998457, 1999998479, 1999998493, 1999998527, 1999998551, 1999998617, 1999998631, 1999998641, 1999998701, 1999998719, 1999998733, 1999998743, 1999998761, 1999998769, 1999998773, 1999998797, 1999998799, 1999998809, 1999998823, 1999998827, 1999998857, 1999998893, 1999998899, 1999998907, 1999998941, 1999998947, 1999998961, 1999999003, 1999999013, 1999999049, 1999999061, 1999999081, 1999999087, 1999999093, 1999999097, 1999999117, 1999999121, 1999999151, 1999999171, 1999999207, 1999999219, 1999999271, 1999999321, 1999999373, 1999999423, 1999999439, 1999999499, 1999999553, 1999999559, 1999999571, 1999999609, 1999999613, 1999999621, 1999999643, 1999999649, 1999999657, 1999999747, 1999999763, 1999999777, 1999999811};
int expresie();
int factor();
int termen();
int expresie()
{
    int sol=termen();
    while(s[ind]=='+' || s[ind]=='-'){
        if(s[ind]=='+'){
            ind++;
            sol=(1LL*sol+termen())%mod;
        }
        else{
            ind++;
            sol=(1LL*sol-termen()+mod)%mod;
        }
    }
    return sol;
}
int termen()
{
    int sol=factor();
    while(s[ind]=='*'){
        ind++;
        sol=(sol*1LL*factor())%mod;
    }
    return sol;
}
int factor()
{
    int sol=0;
    if(s[ind]=='('){
        ind++;
        sol=expresie();
        ind++;
    }
    else{
        if(s[ind]=='['){
            ind++;
            sol=expresie();
            sol=(sol*1LL*sol)%mod;
            ind++;
        }
        else{
            if(s[ind]=='+'){
                ind++;
                sol=expresie();
            }
            else{
                if(s[ind]=='-'){
                    ind++;
                    sol=-expresie();
                    sol=(1LL*sol+mod)%mod;
                }
                else{
                    sol=valmod[s[ind]-'a'+1];
                    ind++;
                }
            }
        }
    }
    return sol;
}
int lgput(int a, int b, int mod)
{
    int p=1;
    while(b){
        if(b%2==1)
            p=(p*1LL*a)%mod;
        a=(a*1LL*a)%mod;
        b>>=1;
    }
    return p;
}
int modulo(int a[], int x)
{
    long long r=0;
    for(int i=a[0]; i>=1; i--){
        r=r*1LL*1000000000+a[i];
        r%=x;
    }
    return (int)r;
}
void atrib(int a[], int x)
{
    a[0]=0;
    for(a[0]=0; x; x/=1000000000)
	a[++a[0]]=x%1000000000;
}
void mult(int a[], int b[])
{
    int c[10000];
    memset(c, 0, sizeof(c));
    int j;
    for(int i=1; i<=a[0]; i++){
        long long t=0;
        for(j=1; j<=b[0] || t; j++,t/=1000000000){
            t+=c[i+j-1]+(j<=b[0]?a[i]*1LL*b[j]:0);
            c[i+j-1]=t%1000000000;
        }
        if(i+j-2>c[0])
            c[0]=i+j-2;
    }
    for(int i=0; i<=c[0]; i++)
        a[i]=c[i];
}
void adun(int a[], int b[])
{
    int c[10000];
    memset(c, 0, sizeof(c));
    int i,t=0;
    for(i=1; i<=a[0] || i<=b[0] || t; i++,t/=1000000000){
        t+=(i<=a[0]?a[i]:0);
        t+=(i<=b[0]?b[i]:0);
        c[i]=t%1000000000;
    }
    c[0]=i-1;
    for(int i=0; i<=c[0]; i++)
        a[i]=c[i];
}
void scad(int a[], int b[])
{
    int c[10005];
    memset(c, 0, sizeof(c));
    for(int i=0; i<=a[0]; i++)
        c[i]=a[i];
    int t=0;
    for(int i=1; i<=a[0]; i++){
        c[i]-=(i<=b[0]?b[i]:0)+t;
        t=0;
        if(c[i]<0){
            c[i]+=1000000000;
            t=1;
        }
    }
    while(c[0]>1 && c[c[0]]==0)
        c[0]--;
    for(int i=0; i<=c[0]; i++)
        a[i]=c[i];
}
int egal(int a[], int b[])
{
    if(a[0]!=b[0])
        return a[0]<b[0];
    for(int i=a[0]; i>=1; i--){
        if(a[i]<b[i])
            return 1;
        if(b[i]<a[i])
            return 0;
    }
    return -1;
}
void afis(int a[])
{
    if(a[0]==0){
        printf("0");
        return;
    }
    printf("%d", a[a[0]]);
    for(int i=a[0]-1; i>0; i--){
        int p=1000000000/10;
        while(p>a[i] && p>1){
            printf("0");
            p/=10;
        }
        printf("%d", a[i]);
    }
}
bool iszero(int a[])
{
    int i;
    for(i=a[0]; i>0 && a[i]==0; i--);
    if(i==0)
        return 1;
    return 0;
}
int main()
{   freopen("eval.in", "r", stdin);
    freopen("eval.out", "w", stdout);
    int n,i,j,sol,l,pinv;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%s", s);
        if(s[0]=='-'){
            for(j=strlen(s); j>1; j-=9){
	    	val[i][0]++;
	    	val[i][val[i][0]]=0;
		for(int k=max(0, j-9); k<j; k++)
		    val[i][val[i][0]]=val[i][val[i][0]]*10+s[k]-'0';
            }
            eneg[i]=1;
        }
        else{
            for(j=strlen(s); j>0; j-=9){
	    	val[i][0]++;
	    	val[i][val[i][0]]=0;
		for(int k=max(0, j-9); k<j; k++)
		    val[i][val[i][0]]=val[i][val[i][0]]*10+s[k]-'0';
            }
        }
    }
    scanf("%s", s);
    for(i=0; i<nrprime; i++){
        mod=kPrimes[i];
        ind=0;
        for(j=1; j<=n; j++){
            valmod[j]=modulo(val[j], mod);
            if(eneg[j]==1)
                valmod[j]=(mod-valmod[j])%mod;
        }
        sol=expresie();
        sol=(sol*1LL+lgput(10, 1000, mod))%mod;
        rest[i]=sol;
    }
    atrib(prime1, kPrimes[0]);
    atrib(rest1, rest[0]);
    for(i=1; i<nrprime; i++){
        atrib(prime2, kPrimes[i]);
        atrib(rest2, rest[i]);
        l=(1LL*modulo(rest2, kPrimes[i])-modulo(rest1, kPrimes[i])+kPrimes[i])%kPrimes[i];
        pinv=lgput(modulo(prime1, kPrimes[i]), kPrimes[i]-2, kPrimes[i]);
        atrib(aux, (l*1LL*pinv)%kPrimes[i]);
        if(iszero(aux)==0){
            mult(aux, prime1);
            adun(rest1, aux);
        }
        mult(prime1, prime2);
    }
    aux1[0]=112;
    for(i=1; i<=111; i++)
        aux1[i]=0;
    aux1[112]=10;
    if(egal(aux1, rest1)==-1)
        printf("0");
    else{
        if(egal(rest1, aux1)==1){
            printf("-");
            scad(aux1, rest1);
            afis(aux1);
        }
        else{
            scad(rest1, aux1);
            afis(rest1);
        }
    }
    return 0;
}