HDU 5238 Calculator 线段树中国剩余定理

题意：

给一个计算器，有一系列计算步骤，只有加，乘，幂三种运算。

有一种查询操作：查询初始值为\(x\)的时候，最终运算结果模\(29393\)的值。

有一种修改操作：可以修改第\(p\)个运算的运算符和运算数。

分析：

分解一下，\(29393=7 \times 13 \times 17 \times 19\)。

所以我们可以维护\(4\)棵线段树，区间维护的信息就是初始值为\(x\)经过这段区间最终得到的值。

然后就用中国剩余定理整合一下。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 50000 + 10;

const int maxnode = maxn * 4;

const int prime[] = { 7, 13, 17, 19 };

int val[4][20][maxnode];

int n, m;

char op[maxn], tmp[5];

int x[maxn];

int pow_mod(int a, int b, int mod) {

    int ans = 1;

    while(b) {

        if(b & 1) ans = ans * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return ans;

}

int calc(int a, char op, int b, int mod) {

    if(op == '+') return ((a + b) % mod);

    if(op == '*') return a * b % mod;

    return pow_mod(a, b, mod);

}

void pushup(int o) {

    for(int i = 0; i < 4; i++)

        for(int j = 0; j < prime[i]; j++) {

            int t = val[i][j][o<<1];

            val[i][j][o] = val[i][t][o<<1|1];

        }

}

void build(int o, int L, int R) {

    if(L == R) {

        for(int i = 0; i < 4; i++)

            for(int j = 0; j < prime[i]; j++)

                val[i][j][o] = calc(j, op[L], x[L], prime[i]);

        return;

    }

    int M = (L + R) / 2;

    build(o<<1, L, M);

    build(o<<1|1, M+1, R);

    pushup(o);

}

void update(int o, int L, int R, int p) {

    if(L == R) {

        for(int i = 0; i < 4; i++)

            for(int j = 0; j < prime[i]; j++)

                val[i][j][o] = calc(j, op[p], x[p], prime[i]);

        return;

    }

    int M = (L + R) / 2;

    if(p <= M) update(o<<1, L, M, p);

    else update(o<<1|1, M+1, R, p);

    pushup(o);

}

void gcd(int a, int b, int& d, int& x, int& y) {

    if(!b) { d = a; x = 1; y = 0; }

    else { gcd(b, a%b, d, y, x); y -= x*(a/b); }

}

int a[4];

int CRT() {

    int M = 29393, d, y, x = 0;

    for(int i = 0; i < 4; i++) {

        int w = M / prime[i];

        gcd(prime[i], w, d, d, y);

        x = (x + y*w*a[i]) % M;

    }

    return (x+M)%M;

}

int main()

{

    int T; scanf("%d", &T);

    for(int kase = 1; kase <= T; kase++) {

        printf("Case #%d:\n", kase);

        scanf("%d%d", &n, &m); getchar();

        for(int i = 1; i <= n; i++) {

            scanf("%c%d", op + i, x + i);

            getchar();

        }

        build(1, 1, n);

        while(m--) {

            int cmd, p;

            scanf("%d%d", &cmd, &p);

            if(cmd == 1) {

                for(int i = 0; i < 4; i++)

                    a[i] = val[i][p%prime[i]][1];

                printf("%d\n", CRT());

            } else {

                getchar();

                scanf("%c%d", op + p, x + p);

                update(1, 1, n, p);

            }

        }

    }

    return 0;

}

巴特西

HDU 5238 Calculator 线段树中国剩余定理

题意：

分析：

最新文章

热门文章

巴特西

HDU 5238 Calculator 线段树 中国剩余定理

题意：

分析：

最新文章

热门文章

HDU 5238 Calculator 线段树中国剩余定理