【2025NOI模拟赛32】涨工资做题记录

给定一张 $n$ 个点 $m$ 条边的无向带权图（可能有重边、自环），有 $q$ 次询问 $(s,t,d,k)$ ，你需要回答如下问题：

一个人从 $s$ 出发，初始有权值 $d$ ，最终要走到 $t$ （可以经过重复点、重复边）；

这个人每经过一条边 $i$ ， $d$ 就会异或上边权 $w_i$ ；

这个人可以在某个点处停下来休息一下，并令 $d\leftarrow 2d$ ，但是最多只能休息 $k$ 次；

求最终 $d$ 的最大值；

$1\le n,m\le 10^5$ ， $1\le q\le 10$ ， $0\le d,w_i< 2^{17}$ ， $0\le k\le 40$ 。

设 $s_i$ 为 $i$ 到根（起点）的异或和， $a_i=(2s_i)\oplus s_i$ ，那么每一次 $\times 2$ 相当于选对应的 $2^{若干}$ 倍 $a_i$ （ $i$ 任意）。

每一次 $\times 2$ 前可以只包含一条返祖边的环的线性基随意组合，所以可以求出每一次选 $a_i$ 可选的集合。

终点选的一定是 $s_t$ 加上线性基。

可行异或和集合为 $2^{k-1}S\oplus\dots\oplus 4S\oplus 2S\oplus S\oplus T$ 这样的形式，其中 $S$ 和 $T$ 都是集合，满足元素在 $[0,2^{18})$ 里，而集合 $A$ 异或集合 $B$ 的结果为 $\{x\oplus y|x\in A,y\in B\}$ 。

然后考虑维护 $\oplus_{i=0}^k 2^iS$ ，每次相当于先整体 $\times 2$ ，再异或上 $S$ 。不难发现 $2^{18}$ 及以上的二进制位对后续的操作是没有影响的，所以由于要最大化异或和，故 $2^{18}$ 位能选 $1$ 就选 $1$ 。那么就可以直接维护 $h_k$ 表示 $\oplus_{i=0}^k 2^iS$ 的高位部分，从而集合大小维持在 $2^{18}$ 内。

那么直接每次做 FWT，时间复杂度是 $O(qkV\log V)$ （ $V$ 为值域），无法通过。

考虑优化，直接维护 FWT 数组：

乘 2：FWT 数组每一个数原地膨胀成两个（1 2 3 变成 1 1 2 2 3 3）；
卷：直接卷；
删掉后一半：还原出原来的两半，判断后一半是否全 $0$ ，是则直接删掉，否则放到前一半；

时间复杂度降为 $O(qV(k+\log V))$ ，可以通过。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

typedef long long ll;

const int p=998244353,inv2=499122177;

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

namespace FWT
{
	const int C[2][2]={{1,1},{1,p-1}},IC[2][2]={{inv2,inv2},{inv2,p-inv2}};	
	inline void FWT(int n,int a[],const int c[2][2])
	{
		for(int len=2;len<=n;len<<=1)
		{
			int mid=len>>1;
			for(int l=0;l<=n-len;l+=len)
			{
				for(int k=0;k<mid;k++)
				{
					int x=a[l+k],y=a[l+mid+k];
					a[l+k]=(1ll*c[0][0]*x%p+1ll*c[0][1]*y%p)%p;
					a[l+mid+k]=(1ll*c[1][0]*x%p+1ll*c[1][1]*y%p)%p;
				}
			}
		}
	}
}

const int S=100005,HB=17,BS=1<<18;

namespace xxj
{
	int a[HB];
	inline void ins(int x)
	{
		for(int i=HB-1;i>=0;i--)
		{
			if(x>>i&1^1) continue;
			if(a[i]==0)
			{
				a[i]=x;
				for(int j=i-1;j>=0;j--) if(a[i]>>j&1) a[i]^=a[j];
				for(int j=i+1;j<=HB;j++) if(a[j]>>i&1) a[j]^=a[i];
				break;
			}
			x^=a[i];
		}
	}
}

int n,m,q;
vector<pair<int,pair<int,int> > > g[S];
bool vis[S];
int sm[S];
int A[BS],tmp[BS];
ll hig[2];
int res[2][BS],re[BS];

void dfs(int u,int fe)
{
	vis[u]=true;
	for(auto t:g[u])
	{
		int v=t.first,w=t.second.first,id=t.second.second;
		if(id==fe) continue;
		if(vis[v]) xxj::ins(sm[v]^sm[u]^w);
		else sm[v]=sm[u]^w,dfs(v,id);
	}
}

inline void slove(int s,int d,int k)
{
	for(int i=0;i<BS/2;i++) res[0][i]=0;
	res[0][sm[s]^d]=1;
	FWT::FWT(BS/2,res[0],FWT::C);
	hig[0]=0;
	for(int i=1;i<=k;i++)
	{
		int u=i&1,v=u^1;
		hig[u]=0;
		memset(res[u],0,sizeof(res[u]));
		hig[u]=hig[v]*2;
		for(int j=0,t=0;j<BS/2;j++)
		{
			res[u][t++]=res[v][j];
			res[u][t++]=res[v][j];
		}
		for(int j=0;j<BS;j++) res[u][j]=1ll*res[u][j]*A[j]%p;
		for(int j=0;j<BS/2;j++)
		{
			int x=res[u][j],y=res[u][j+BS/2]; // x+y x-y
			res[u][j]=1ll*((ll)x+y)*inv2%p;
			res[u][j+BS/2]=1ll*((ll)x-y+p)*inv2%p;
		}
		bool fl=false;
		for(int j=BS/2;j<BS&&!fl;j++) fl|=res[u][j]!=0;
		if(fl)
		{
			// printf(">> %d\n",i);
			hig[u]+=1<<HB;
			for(int j=0;j<BS/2;j++) res[u][j]=res[u][j+BS/2];
		}
	}
}

int main()
{
	freopen("wage.in","r",stdin);
	freopen("wage.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int ct;
	cin>>ct;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		g[x].emplace_back(y,make_pair(w,i));
		g[y].emplace_back(x,make_pair(w,i));
	}
	dfs(1,0);
	tmp[0]=1;
	for(int i=0;i<HB;i++) tmp[xxj::a[i]*2]=1;
	for(int i=1;i<=n;i++) A[((sm[i])*2)^sm[i]]=1;
	FWT::FWT(BS,tmp,FWT::C),FWT::FWT(BS,A,FWT::C);
	for(int i=0;i<BS;i++) A[i]=1ll*A[i]*qpow(tmp[i],HB)%p;
	for(int i=0;i<BS/2;i++) tmp[i]=0;
	tmp[0]=1;
	for(int i=0;i<HB;i++) tmp[xxj::a[i]]=1;
	FWT::FWT(BS/2,tmp,FWT::C);
	for(int i=0;i<BS/2;i++) tmp[i]=qpow(tmp[i],HB);
	while(q-->0)
	{
		int s,t,d,k;
		cin>>s>>t>>d>>k;
		slove(s,d,k);
		for(int i=0;i<BS/2;i++) re[i]=0;
		re[sm[t]]=1;
		FWT::FWT(BS/2,re,FWT::C);
		for(int i=0;i<BS/2;i++) re[i]=1ll*re[i]*tmp[i]%p*res[k&1][i]%p;
		FWT::FWT(BS/2,re,FWT::IC);
		ll ans=0;
		for(int i=0;i<BS/2;i++) if(re[i]!=0) ans=i+hig[k&1];
		cout<<ans<<'\n';
	}
	return 0;
}
/*
设 s_i 为 i 到根（起点）的 xor，a_i=(2s_i)^s_i
那么每一次 *2 相当于选对应的 2^{若干} 倍 a_i（i任意）
每一层可以线性基随意组合，所以可以求出每一次选 a_i 可选的集合
终点选的一定是 s_t 加上线性基，要特判
可行 xor 和集合为 {8S}^{4S}^{2S}^{S}^{T} 这样的形式
其中 S 和 T 都是集合，满足元素在 [0,2^19) 里
S 最多乘上 2^{k-1}
晓晴觉得线性基可以最后滚，因为没有基的位只有17位
没想到这个性质
但是没用的，高位会影响到线性基的这位用不用
这是劳累的
集合幂级数相关？
*/

【2025NOI模拟赛32】涨工资 做题记录

感谢您的支持，我会继续努力的!

【2025NOI模拟赛32】涨工资做题记录