hdu_5238 Calculator

题目:

  Sakura has invented a new kind of calculator that can evaluate expressions. This calculator maintains a serial of operators and numbers inside. All these numbers and operators form an ordered table. For example
  ∗4+2^3+8∗6
  is a possible table. The calculator also supports the following two operations.
  1. 1 x.
  This corresponds to the evaluation operation. For instance, if x=2, together with the table being the one described above, the calculator will output
  ((((2∗4)+2)3)+8)∗6=6048.
  As for x=3, it will output
  ((((3∗4)+2)3)+8)∗6=16512.
  2. 2 p cx.
  This corresponds to the modification operation. The calculator will change the p-th term in the expression to cx. Here c denotes an operator while x denotes a number.
  For example, if p=3 and cx=∗5, the expression will become
  ∗4+2∗5+8∗6.
  Now you are asked to implement this calculator. However, for technical reasons, you should just output the result modulo 29393. It is guaranteed that, in all terms appeared in the input data, c∈{+,∗,^}, 0≤x<29393.

思路:

  可以用线段树维护一段算式。
  用保存结点输入时返回的值。
  那么
  因为
  所以可以用多棵线段树分别维护膜这几个值的结果,再用中国剩余定理求出膜的结果就行了。

代码:

#include <bits/stdc++.h>
#define ll long long
#define MAXN 50005
using namespace std;
int pow(int x,int k,int mod){
    int ans=1;
    while(k){
        if(k&1)(ans*=x)%=mod;
        (x*=x)%=mod;
        k>>=1;
    }
    return ans;
}
const int mod[]={7,13,17,19};
int tre[MAXN<<2][4][25];
void upd(int o,char op,int a){
    for(int k=0;k<4;k++)
        for(int i=0;i<mod[k];i++)
            if(op=='+')
                tre[o][k][i]=(i+a)%mod[k];
            else if(op=='*')
                tre[o][k][i]=(i*a)%mod[k];
            else
                tre[o][k][i]=pow(i,a,mod[k]);
}
#define ls o<<1,L,mid
#define rs o<<1|1,mid+1,R
void pushup(int o){
    for(int k=0;k<4;k++)
        for(int i=0;i<mod[k];i++)
            tre[o][k][i]=tre[o<<1|1][k][tre[o<<1][k][i]];
}
void update(int w,char op,int a,int o,int L,int R){
    if(L==R){
        upd(o,op,a);
        return;
    }
    int mid=L+R>>1;
    if(w<=mid)
        update(w,op,a,ls);
    else
        update(w,op,a,rs);
    pushup(o);
}
#define read(c) \
        do c=getchar(); \
        while(c!='*'&&c!='+'&&c!='^');
void build(int o,int L,int R){
    if(L==R){
        int a;char c;
        read(c);scanf("%d",&a);
        upd(o,c,a);
        return;
    }
    int mid=L+R>>1;
    build(ls);build(rs);
    pushup(o);
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll calc(ll a,ll b,ll c){
    ll x,y,d;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    a/=d;b/=d;c/=d;
    return (x*c%b+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int T,n,m;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        printf("Case #%d:\n",t);
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--){
            int f,w;
            char c;
            scanf("%d%d",&f,&w);
            if(f==1){
                CRT crt;
                for(int i=0;i<4;i++)
                    crt.insert(tre[1][i][w%mod[i]],mod[i]);
                printf("%lld\n",crt.A);
            }
            else {
                int x;char c;
                read(c);
                scanf("%d",&x);
                update(w,c,x,1,1,n);
            }
        }
    }
    return 0;
}