P2174 题解

· · 题解

不会离线和高级数据结构和中国剩余定理的人的福音!

Update 2020.6.26 21:00: 使用了离散化,防止在D操作中被卡O(n^2log_2(n))

你以为这题要么离线,要么高级数据结构,要么中国剩余定理这三种解法吗?

其实还有一种解法!

题目里只有五种操作,下面我们一个个来剖析这几种操作.

Part A:最大值

要求最大值,我们可以用一个排好序的数组的最后一个元素的下标b(biggest)来存储.

当这个数不复存在时,显然在剩下的元素中的最大值的下标比b要小.

那我们只要简单地向左一个个地缩小范围,直到找到一个还存在的元素即可.

Part B:最小值

最小值跟最大值不是可以用同样的方法嘛,只不过反过来而已,我们用s(smallest)来表示最小值元素的下标.

Part C:a_b^{a_s}\mod317847191

这不就是把上面两个玩意合在一起加个快速幂吗,没什么好讲的,略.

Part D:\prod x(x\in A)\mod317847191

这自然成为了这种解法最复杂的地方.

自然容易想到使用一个变量sum来存储这个答案,然后使用乘法逆元来当作删除.

但是远没有这么简单,因为我们的模数317847191并不是一个质数,有一部分的数字是没有模317847191意义下的乘法逆元的.

比如说,因为317847191=71\times113\times173\times229,所以说因数中有71,113,173,229的数字都是没有模317847191意义下的逆元的.

那怎么办?

我马上就想到把这几个因子从sum中单独提取出来,在最后的时候统一处理.

可以得到一个式子:

\prod x(x\in A)\equiv sum\times71^{t_{71}}\times113^{t_{113}}\times173^{t_{173}}\times229^{t_{229}}\pmod{317847191}

其中t_x表示因子x出现的次数.

但是,毒瘤的出题人肯定不愿意让我们一点思考都没有就让我们过.

显然还要继续找方法优化,但是我们可以从哪里入手呢? 现在我们计算一次这个式子需要计算$4$次快速幂,有没有方法可以减少计算快速幂的次数吗? 答案是有的. 下面有一个引理: $$ p_b^a\bmod\prod_{i=1}^np_i=p_b\times(p_b^{a-1}\bmod(\frac{\prod_{i=1}^np_i}{p_b})) $$ 其中$p_i$是质数,且$p_i\not=p_j(i\not=j)$. #### 证明: 我们在小学二年级就学过:若$a\div b=c\cdots\cdots d$,则$ae\div be=c\cdots\cdots de$. 那我们把这个式子套进去就可以了,我们不用管$c$,令$a=p_b^{a-1},b=\frac{\prod_{i=1}^np_i}{p_b},d=p_b^{a-1}\bmod(\frac{\prod_{i=1}^np_i}{p_b}),e=p_b$. 则可以得到$a\bmod b=d,(ae)\bmod(be)=de$. 那么就有$(ae)\bmod(be)=de=e\cdot(a\bmod b)$. 即可得$(p_b^{a-1}\cdot p_b)\bmod(\frac{\prod_{i=1}^np_i}{p_b}\cdot p_b)=p_b\cdot(p_b^{a-1}\bmod\frac{\prod_{i=1}^np_i}{p_b})$. 即$p_b^a\bmod\prod_{i=1}^np_i=p_b\cdot(p_b^{a-1}\bmod\frac{\prod_{i=1}^np_i}{p_b})$. $Q.E.D.

好,现在就可以直接用这个玩意来先代入了.

\prod x(x\in A)\equiv sum\times(71\times(71^{t_{71}-1}\bmod(\frac{317847191}{71})))\times(113\times(113^{t_{113}-1}\bmod(\frac{317847191}{113})))\times(173\times(173^{t_{173}-1}\bmod(\frac{317847191}{173})))\times(229\times(229^{t_{229}-1}\bmod(\frac{317847191}{229})))\pmod{317847191}

也可以简写为:

\prod x(x\in A)\equiv sum\times\prod_{p_i|317847191}(p_i\times(p_i^{t_{p_i}-1}\bmod(\frac{317847191}{p_i})))\pmod{317847191}

其中p_i是质数,且p_i\not=p_j(i\not=j).

可是这样算还是要算快速幂啊.

但是,我们可以发现p_i在取模\frac{317847191}{p_i}意义下已经是有乘法逆元的了.

所以我们可以预先算好p_i^{t_{p_i}-1}\bmod\frac{317847191}{p_i}的值,用s_i存储,要加一个数就乘以p_i,要删一个数就乘以p_i在取模\frac{317847191}{p_i}意义下的乘法逆元.

这样就可以O(1)处理了.

代码如下:

//This code was made by Chinese_zjc_.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_map>
#include<queue>
#define int long long//小心爆零
#define INF 0x3fffffffffffffff
#define MOD 317847191
using namespace std;
const int q71=1387153,q113=1020576,q173=785883,q229=1248575;//预先算好四个特殊数字的相应逆元
int n,m,tmp,b,s,sum=1,x,y,a[1000001],cnt,s71=q71,s113=q113,s173=q173,s229=q229,ans71,ans113,ans173,ans229,t71,t113,t173,t229;
//n,m,a如题意所述;
//b,s,sxxx,txxx如上文所述;
//tmp是暂存用的工具变量;
//sum是除了四个特殊值外的总乘积;
//x,y是用在exgcd里的变量,exgcd完后x是X模Y意义下的逆元;
//ansxxx表示xxx在T操作里的贡献;
//cnt表示集合里不重复元素的总个数(包括删掉的);
struct NUM{
    int v,t;
}num[1000001];//离散化,把重复的放到一起方便删除
char c;//工具变量
inline int power(int A,int B,int C)//快速幂&cdd(不是)
{
    int TMP=1;
    while(B)
    {
        if(B&1)
        {
            TMP=(TMP*A)%C;
        }
        B>>=1;
        A=(A*A)%C;
    }
    return TMP;
}
inline void exgcd(int X,int Y)//算乘法逆元用
{
    if(Y==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(Y,X%Y);
    int TMP=x;
    x=y;
    y=TMP-X/Y*y;
}
inline void d(int now)//删除操作,通过二分找到一个还没被删掉的,把used标记打成true
{
    int l=s,r=b,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(num[mid].v<now)
        {
            l=mid+1;
            continue;
        }
        if(num[mid].v>now)
        {
            r=mid-1;
            continue;
        }
        if(num[mid].v==now)
        {
            --num[mid].t;
            return;
        }
    }
    --num[l].t;
}
inline void write(int now)//快写
{
    if(now==0)
    {
        putchar('0');
    }
    char s[100];
    int len=0;
    while(now)
    {
        s[len++]=now%10+'0';
        now/=10;
    }
    while(len)
    {
        putchar(s[--len]);
    }
    putchar('\n');
}
inline void read(int &now)//快读数字
{
    now=0;
    char cc=getchar();
    while('0'>cc||'9'<cc)
    {
        cc=getchar();
    }
    while('0'<=cc&&cc<='9')
    {
        now=(now<<3)+(now<<1)+(cc^'0');
        cc=getchar();
    }
}
inline void rd(char &now)//快读字符
{
    now=getchar();
    while('A'>now||now>'Z')
    {
        now=getchar();
    }
}
signed main()
{
    read(n);
    read(m);
    for(int i=1;i<=n;++i)
    {
        read(a[i]);
        tmp=a[i];
        //特殊处理几个特殊数字并提出因子
        while(tmp%71==0)
        {
            ++t71;
            s71=s71*71%(MOD/71);
            tmp/=71;
        }
        while(tmp%113==0)
        {
            ++t113;
            s113=s113*113%(MOD/113);
            tmp/=113;
        }
        while(tmp%173==0)
        {
            ++t173;
            s173=s173*173%(MOD/173);
            tmp/=173;
        }
        while(tmp%229==0)
        {
            ++t229;
            s229=s229*229%(MOD/229);
            tmp/=229;
        }
        sum=(sum*tmp)%MOD;//把剩下的其它数字直接丢一起
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;++i)
    {
        if(a[i]!=num[cnt].v)
        {
            num[++cnt].v=a[i];
        }
        ++num[cnt].t;
    }
    s=1;
    b=cnt;
    while(m)
    {
        --m;
        rd(c);
        if(c=='D')//删除
        {
            read(tmp);
            d(tmp);
            while(tmp%71==0)
            {
                --t71;
                s71=s71*q71%(MOD/71);
                tmp/=71;
            }
            while(tmp%113==0)
            {
                --t113;
                s113=s113*q113%(MOD/113);
                tmp/=113;
            }
            while(tmp%173==0)
            {
                --t173;
                s173=s173*q173%(MOD/173);
                tmp/=173;
            }
            while(tmp%229==0)
            {
                --t229;
                s229=s229*q229%(MOD/229);
                tmp/=229;
            }
            exgcd(tmp,MOD);
            sum=(sum*(x%MOD+MOD))%MOD;
        }
        if(c=='B')//最大值
        {
            while(!num[b].t)
            {
                --b;
            }
            write(num[b].v);
        }
        if(c=='S')//最小值
        {
            while(!num[s].t)
            {
                ++s;
            }
            write(num[s].v);
        }
        if(c=='M')//a[b]^a[s] mod MOD
        {
            while(!num[b].t)
            {
                --b;
            }
            while(!num[s].t)
            {
                ++s;
            }
            write(power(num[b].v,num[s].v,MOD));
        }
        if(c=='T')//总乘积
        {
            //t为0时是唯一的ans为1的时候,特判处理
            if(t71)
            {
                ans71=71*s71;
            }
            else
            {
                ans71=1;
            }
            if(t113)
            {
                ans113=113*s113;
            }
            else
            {
                ans113=1;
            }
            if(t173)
            {
                ans173=173*s173;
            }
            else
            {
                ans173=1;
            }
            if(t229)
            {
                ans229=229*s229;
            }
            else
            {
                ans229=1;
            }
            write(sum*ans71%MOD*ans113%MOD*ans173%MOD*ans229%MOD);//得到答案
        }
    }
    return 0;
}