2025_10_22 T3

· · 题解

感觉非常精妙的 trick，考场上没想到也确实在情理之中

话说这操作只有三种，单点加，子集加，超集加，询问只有一种，询问子集和，先考虑单点加的情形：

容易发现，若暴力解决，修改只需 O(1)，而求和需要枚举子集，需要 O(2^n)，瓶颈显然在于后者，故尝试平衡两者的时间消耗，立马尝试折半。我们假设所加或查询的数的下标为 S，高位的一半为 S1，低位的一半为 S2,于是顺理成章地设置数组 f_{i,j}，表示高位为 i，低位为 j 的子集的数之和

修改时，我们固定 S1，枚举 S2 的超集 j，为所有 f_{S1,j} 加上所加的数，查询时固定 S2，枚举 S1 的子集 i，使答案加上所有 f_{i,S2} 即可

发现超集及子集加的情况同单点类似，只是求贡献时要带权值，所以开数组 g_{i,j},h_{i,j}，分别记录两者的值，定义同上

对于超集加，修改时枚举 g_{S1,j} ，其中 j 是 S2 的超集，加贡献的系数便是 2^{j \oplus S2}，查询同理

对于子集加，修改时枚举 j(j \cap S2 \ne \emptyset),使 h_{S1,j} 加上，系数为 2^{j \& S2}

答案即为三者之和

时间复杂度 O(q\times 2^{\frac{n}{2}})

#include<bits/stdc++.h>
using namespace std;
const int maxv=2e1+5,maxn=1.1e6,maxm=1e3+30,Mod=998244353;
int n,q;
int pow_2[maxv],num[maxn],f[3][maxm][maxm];
int add(int x,int y) {return x+y>=Mod?x+y-Mod:x+y;}
int read()
{
    int ret=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*w;
}
void pre_all()
{
    pow_2[0]=1;
    for(int i=1;i<maxv;i++) pow_2[i]=pow_2[i-1]<<1;
    for(int i=0;i<maxn;i++) for(int j=0;j<maxv;j++) num[i]+=(i&pow_2[j])?1:0;
}
void inpu() {n=read(),q=read();}
void deal()
{
    n=((n&1)+n)>>1;
    int opt,S,c,a,b;
    while(q--)
    {
        opt=read();
        S=read();
        a=S>>n,b=S&(pow_2[n]-1);
        if(!opt)
        {
            int ans=0;
            for(int i=a;;i=(i-1)&a)
            {
                ans=add(ans,f[0][i][b]);
                ans=add(ans,1ll*f[1][i][b]*pow_2[num[a^i]]%Mod);
                if(!i) break;
            }
            for(int i=0;i<pow_2[n];i++) ans=add(ans,1ll*f[2][i][b]*pow_2[num[i&a]]%Mod);
            printf("%d\n",ans);
        }else if(opt==1)
        {
            c=read();
            int up=(pow_2[n]-1)^b;
            for(int i=up;;i=(i-1)&up)
            {
                f[0][a][b|i]=add(f[0][a][b|i],c);
                if(!i) break;
            }
        }else if(opt==2)
        {
            c=read();
            int up=(pow_2[n]-1)^b;
            for(int i=up;;i=(i-1)&up)
            {
                f[1][a][b|i]=add(f[1][a][b|i],1ll*c*pow_2[num[i]]%Mod);
                if(!i) break;
            }
        }else
        {
            c=read();
            for(int i=0;i<pow_2[n];i++) f[2][a][i]=add(f[2][a][i],1ll*c*pow_2[num[i&b]]%Mod);
        }
    }
}
void solve()
{
    inpu();
    deal();
}
int main()
{
    pre_all();
    int t=1;
    while(t--) solve();
    return 0;
}