Cod sursa(job #2098538)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 2 ianuarie 2018 22:55:29
Problema Eval Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("eval.in");
ofstream fout ("eval.out");

const int base = 10000, primes = 115, sigma = 30;
typedef long long ll;
typedef vector<int> big_number;

int p[] = {1073741789,1073741783,1073741741,1073741723,1073741719,1073741717,1073741689,1073741671,1073741663,1073741651,1073741621,1073741567,1073741561,1073741527,1073741503,1073741477,1073741467,1073741441,1073741419,1073741399,1073741387,1073741381,1073741371,1073741329,1073741311,1073741309,1073741287,1073741237,1073741213,1073741197,1073741189,1073741173,1073741101,1073741077,1073741047,1073740963,1073740951,1073740933,1073740909,1073740879,1073740853,1073740847,1073740819,1073740807,1073740793,1073740783,1073740781,1073740697,1073740693,1073740691,1073740649,1073740609,1073740571,1073740567,1073740543,1073740541,1073740537,1073740529,1073740523,1073740517,1073740501,1073740489,1073740477,1073740463,1073740439,1073740403,1073740391,1073740379,1073740249,1073740201,1073740189,1073740183,1073740177,1073740163,1073740147,1073740139,1073740133,1073740127,1073740123,1073740079,1073740067,1073740061,1073740049,1073740013,1073739983,1073739949,1073739937,1073739917,1073739911,1073739893,1073739883,1073739881,1073739859,1073739853,1073739817,1073739767,1073739749,1073739739,1073739721,1073739683,1073739679,1073739649,1073739631,1073739619,1073739617,1073739599,1073739577,1073739559,1073739523,1073739493,1073739473,1073739451,1073739449,1073739437,1073739421};
int n, Mod, i, val[sigma], w[primes + 5], ans[primes + 5], pos;
string s, Nr[sigma];

int add(int x, int y) {x+=y; return x<Mod ? x : x-Mod;}
int inm(int x, int y) {return (ll) x*y%Mod;}

big_number operator * (big_number a, int b)
{
  //  cerr << "Inmultire\n";
  //  for(auto cif : a) cerr << cif << ' '; cerr << '\n';

    big_number ans;
    ll t = 0;

    for(auto cif : a)
    {
        t += (ll) cif * b;
        ans.push_back(t % base);
        t /= base;
    }

    while(t)
        ans.push_back(t % base), t /= base;

    while(ans.size() && !ans.back()) ans.pop_back();

  //  for(auto cif : ans) cerr << cif << ' '; cerr << '\n';
    return ans;
}

big_number operator + (big_number a, big_number b)
{
 //   cerr << "Adunare\n";
  //  for(auto cif : a) cerr << cif << ' '; cerr << '\n';
   // for(auto cif : b) cerr << cif << ' '; cerr << '\n';

    big_number ans;
    int i, t = 0;

    if(a.size() > b.size()) swap(a, b);
    a.resize(b.size());

    for(i=0; i<a.size(); ++i)
    {
        t += a[i] + b[i];
        ans.push_back(t % base);
        t /= base;
    }

    while(t)
        ans.push_back(t % base), t /= base;

  //  for(auto cif : ans) cerr << cif << ' '; cerr << '\n';

    return ans;
}

big_number operator - (big_number a, big_number b)
{
    big_number ans;
    int i;

    for(i=0; i<b.size(); ++i)
    {
        if(a[i] < b[i]) a[i] += base, a[i+1] --;
        ans.push_back(a[i] - b[i]);
    }

    for(; i<a.size(); ++i) ans.push_back(a[i]);
    return ans;
}

void refresh_val()
{
    int i, j; bool sgn;
    for(i=0; i<n; ++i)
    {
        val[i] = 0;

        if(Nr[i][0] == '-') sgn = 1, j = 1;
            else
            {
                sgn = 0; j = 0;
                if(Nr[i][0] == '+') ++j;
            }

        for(; j<Nr[i].size(); ++j)
            val[i] = add( inm(val[i], 10) , Nr[i][j] - '0');

        if(sgn) val[i] = (Mod - val[i]) % Mod;
    }
}

int power(int a, int b)
{
    if(!b) return 1;
    if(b&1) return inm(a, power(inm(a,a), b/2));
    return power(inm(a,a), b/2);
}

void TCR()
{
    int i, j, prod, sum;
    for(i=0; i<primes; ++i)
    {
        prod = 1; sum = 0; Mod = p[i];
        for(j=0; j<i; ++j)
        {
            sum = add(sum, inm(prod, w[j]));
            prod = inm(prod, p[j]);
        }

        sum = add(ans[i], Mod - sum);
        w[i] = inm(sum, power(prod, Mod - 2));
    }
}

void solve()
{
    big_number prod, ans;
    prod.push_back(1);

    for(i=0; i<primes; ++i)
    {
        ans = ans + prod * w[i];
        prod = prod * p[i];
    }

    if(ans.size() > 250) fout << '-', ans = prod - ans;

    while(ans.size() && !ans.back()) ans.pop_back();
    if(ans.empty())
    {
        fout << "0\n";
        return;
    }

    fout << ans.back(); ans.pop_back();
    reverse(ans.begin(), ans.end());
    for(auto cif : ans)
        fout << cif / 1000 << cif / 100 % 10 << cif / 10 % 10 << cif % 10;
    fout << '\n';
}

int termen();
int eval();
int number();

int main()
{
    fin >> n;
    for(i=0; i<n; ++i) fin >> Nr[i];
    fin >> s;

    for(i=0; i<primes; ++i)
    {
        Mod = p[i];
        refresh_val();
        pos = 0;
        ans[i] = eval();
    }

    TCR();
    solve();

    return 0;
}

int number()
{
    if(s[pos] == '[')
    {
        ++pos;
        int res = eval();
        ++pos;
        return inm(res, res);
    }

    if(s[pos] == '-')
    {
        ++pos;
        return inm(Mod - number(), 1);
    }

    if(s[pos] == '+')
    {
        ++pos;
        return number();
    }

    if(s[pos] == '(')
    {
        ++pos;
        int res = eval();
        ++pos;
        return res;
    }

    return val[s[pos++] - 'a'];
}

int termen()
{
    int x = number();
    while(s[pos] == '*')
    {
        ++pos;
        x = inm(x, number());
    }
    return x;
}

int eval()
{
    int x, res;
    x = termen();
    while(s[pos] == '+' || s[pos] == '-')
    {
        bool what = (s[pos] == '+');
        ++pos;
        res = termen();
        if(what) x = add(x, res);
            else x = add(x, Mod - res);
    }
    return x;
}