题解 P4588 【[TJOI2018]数学计算】

· · 题解

看各位dalao代码都好长啊（无喷人之意）······

这题其实代码珂以肥肠肥肠短。

juruo来提供一下，给不想在这题上花费过多时间的dalao一种新写法。

诶好像是不是你谷只有我是快省选了线段树板子还是不会背所以需要一个短代码。

首先思路：

思路一：膜你+高精。

算了下，空间······

python也不行，人生苦短py溢出。

思路二：稍好的膜你。

就是一路取膜，除法转逆元。

但这题毒瘤膜数不是质数啊喂~

而且还要特判被整除的情况。

其实也许珂以中剩一波（

不管了。

思路三：更好的膜你。

想想，每次改一个数就要重算。

而其他都是我们之前计算过的，只有一项不一样。

每次重算，值得吗？

怎么避免？

再想想，每次的数后面计算需要肯定要存下来。

相当于一个序列。

要支持什么？

想想······

更改一个数，查询总乘积？

抽象一点······

点更新，段查询！！！

（是不是异常熟悉？）

BIT/线段树。

这题BIT不太行，因为有除法。

所以正解出来了：线段树。

不想打超长代码怎么办？

非递归！

有个好东西zkw树正好可用~

于是这题······终于没了。

最后贴代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int d[4000009];
int n,M,T,mod,p;
signed main(){
    for(scanf("%lld",&T);T;--T){
        scanf("%lld%lld",&n,&mod);
        for(M=1;M<=n;M<<=1);
        fill(d+1,d+M+n+2,1);//注意！！！一定要多fill一个，否则QAQ行可能有问题。
        for(int i=1,a=0,b=0;i<=n;++i){
            scanf("%lld%lld",&a,&b);
            a==1?d[p=i+M]=b%mod:d[p=b+M]=1;
            while(p>>=1)d[p]=d[p<<1]*d[p<<1|1]%mod;//QAQ
            printf("%lld\n",d[1]);
        }
    }
    return 0;
}

祝大家切题愉快！