P4588

Aryper · 2021-07-28 21:03:28 · 个人记录

[TJOI2018]数学计算

本质是线段树。。。

问题是为什么不能求逆元。其实费马小定理求逆元必须满足模数是质数，而乘法逆元存在的条件是该数与模数互质。显然这题一个条件也不满足。。。

所以其实这题就是强迫做一个暴力优化，显然线段树是一个不错的选择。

线段树的写法相当暴力，将每次操作视为单点修改，每次输出视为求区间乘积。

时间复杂度 O(tq\log q) 。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e5;

struct segment_tree{
    ll l,r,mul;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define mul(x) tree[x].mul
}tree[N*4+5];

ll T,q,mo,type,x;

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) {mul(p)=1;return;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
    mul(p)=(mul(p*2)*mul(p*2+1))%mo;
}

void change(ll p,ll pos,ll x) {
    if(l(p)==r(p)) {mul(p)=x;return;}
    ll mid=(l(p)+r(p))>>1;
    if(pos<=mid) change(p*2,pos,x);
    if(pos>mid) change(p*2+1,pos,x);
    mul(p)=(mul(p*2)*mul(p*2+1))%mo;
}

ll getmul(ll p,ll l,ll r) {
    if(l<=l(p)&&r>=r(p)) return mul(p);
    ll mid=(l(p)+r(p))>>1;
    ll res=1;
    if(l<=mid) res=(res*getmul(p*2,l,r))%mo;
    if(r>mid) res=(res*getmul(p*2+1,l,r))%mo;
    return res%mo;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    T=read();

    while(T--) {
        q=read();mo=read();
        build(1,1,q);
        for(ll i=1;i<=q;i++) {
            type=read();x=read();
            if(type==1) {
                change(1,i,x);
                write(getmul(1,1,i)%mo);putchar('\n');
            }
            if(type==2) {
                change(1,x,1);
                write(getmul(1,1,i)%mo);putchar('\n');
            }
        }
    }

    return 0;
}