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}})

CPP

#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;
}

文章操作

相关推荐

评论

2025_10_22 T3