Cod sursa(job #918469)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 21:45:20
Problema Eval Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <stdio.h>
#include <map>
 
using namespace std;
 
#define MAX_PRIMES 120
#define MAX_VAR 26
#define MAX_LEN 1500
#define MAX_EXPR 100005
#define FIN "eval.in"
#define FOUT "eval.out"
#define ll long long
 
int N, P[MAX_PRIMES], R[MAX_PRIMES], V[MAX_VAR], p, MOD, p1[MAX_LEN], r1[MAX_LEN], p2[MAX_LEN], r2[MAX_LEN];
char var[MAX_VAR][MAX_LEN], expr[MAX_EXPR];
map<int, bool> H;
 
inline int is_prime(int n)
{
    int i;
 
    if (!(n%2)) return 0;
    for (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(void);
int term(void);
int factor(void);
 
int eval(void)
{
    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(void)
{
    int ret = factor();
 
    while (expr[p] == '*')
    {
        p++;
        mul(ret, factor());
    }
    return ret;
}
 
 
int factor(void)
{
    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 big_mod(int a[], int b)
{
    int i, ret = 0;
 
    for (i = a[0]; i > 0; i--)
        ret = ((ll) ret*10 + a[i]) % b;
    return ret;
}
 
void big_add(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 big_sub(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 big_mul(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 big_mul(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];
 
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
 
    scanf("%d\n", &N);
    for (i = 0; i < N; i++)
        scanf("%s\n", var[i]);
    fgets(expr, sizeof(expr), stdin);
 
    for (i = 0; i < MAX_PRIMES; 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 < MAX_PRIMES; i++)
    {
        init(p2, P[i]); init(r2, R[i]);
 
        a = big_mod(r2, P[i]) - big_mod(r1, P[i]);
        while (a < 0) a += P[i];
        b = pow(big_mod(p1, P[i]), P[i]-2, P[i]);  
        k = ((ll)a * b) % P[i];
 
        if (k)
        {
            memcpy(t, p1, sizeof(p1));
            big_mul(t, k); big_add(r1, t);
        }
        big_mul(p1, p2);
    }
 
    memset(t, 0, sizeof(t));
    t[0] = 1001; t[1001] = 1;
    if (r1[0] < 1001)
    {
        big_sub(t, r1);
        memcpy(r1, t, sizeof(t));
        printf("-");
    } else big_sub(r1, t);
 
    for (i = r1[0]; i > 0; i--)
        printf("%d", r1[i]);
    printf("\n");
 
    return 0;
}