AGC031F Walk on Graph

AGC031F

给你一个有\(n\)个点\(m\)条边的无向图。

\(Q\)次询问,每次询问\(S\)到\(T\),是否有路径的权值恰好为\(R\)。

路径权值的定义:\(\sum_{i=1}^k2^{i-1}c_i \mod MOD\),\(c_i\)表示经过的第\(i\)条边的边权。

\(MOD\)给定。\(MOD\le 10^6\)

\(n,m,Q\le 5*10^4\)


神仙题。

首先感觉正着做要记第几个,不太优美,考虑反着做。记状态为\((a,x)\)表示到达了点\(a\),权值为\(x\)。一次经过边\((a,b,c)\)的转移可以到达\((b,2x+c)\)。

接下来分析一波性质:

性质一:

假如在边\((a,b,c)\)来回走动:\((a,x)\to (b,2x+c) \to (a,4x+3c) \to \dots\)。走\(i\)次权值为\(2^ix+(2^i-1)c\)。若干次(具体来说是\(2\)在模\(MOD\)意义下的秩次)后,权值就会回到\(x\)。这时候点可能在\(a\)或\(b\),如果这个时候位置在\(b\),再走这么多次位置就会回到\(a\)。

于是可以发现\((b,2x+c)\)是可以到达\((a,x)\)的。那么\((a,x)\)和\((b,2x+c)\)之间连的是双向边

如果我们将所有状态建出一个图,那么问题就是判断\((T,0)\)和\((S,R)\)是否在同一个连通块。

性质二:

假如现在的权值是\(x\),和当前所在的点(记为\(u\))相连的边有两条长度为\(a\)和\(b\)的边。

分别来回走一趟,分别可以得到\(4x+3a\)和\(4x+3b\)。

换元,将\(4x+3a\)变成\(x\),那么\(x\)和\(x+3(b-a)\)是联通的

将这个性质扩展一下:一个在远处的点\(v\),和它相连的有两条长度为\(a\)和\(b\)的边。现在在点\(u\),权值\(x\)和\(x+3(b-a)\)是联通的。 考虑如此构造:任选一条从\(u\)到\(v\)路径走过去,权值形如\(2^kx+\sum_{i=1}^k2^{i-1}c_i\),然后根据前面的结论变成\(2^kx+\sum_{i=1}^k2^{i-1}c_i+2^k*3(b-a)\)。按照先前的路径回退回去(如性质一,即\((b,2x+c)\)到\((a,x)\))。这样最终到达状态\((u,x+3(b-a))\)。

再扩展:选取的这两条边可以是任意的两条边。 假如\(u\)和\(v\)之间有一条权值为\(b\)的边,考虑选取和\(u\)相连的两条边\(a,b\)与和\(v\)相连的两条边\(b,c\),那么可以从\(x\)得到\(x+3(b-a)+3(c-b)=x+3(c-a)\)。如果不直接相连,可以类似地扩展。

性质三:

设\(g=\gcd_{a,b\in E}(a-b)\)。其中\(a-b\)是模\(MOD\)意义下的。

可以证明\(g|MOD\):由于\(g|((a-b)\mod MOD),g|((b-a) \mod MOD)\),所以\(g|MOD\)。

那么把\(\gcd(3g,MOD)\)作为新的模数,是可以替代原问题的。因为由数论知识得每个状态的权值可以任意加减\(3g\)。

显然\(gcd(3g,MOD)=g或3g\)。

接下来是做法:

显然所有边的边权模\(g\)的值是相同的,记为\(z\)。

将所有边权减\(z\),状态中的权值加\(z\)。

可以发现这样转换之后问题是不变的:\((a,x)\to (a,x+z)' \to (b,2(x+z)+c-z)'=(b,2x+c+z)'\to (b,2x+c)\)

(后面不把\('\)写出来了,这里只是为了方便区分)

考虑从\((u,x)\)出发,到达的状态一定可以表示成这样的形式:\((v,2^px+qg)\)

显然\(q\in \{0,1,2\}\)。

由于有\((a,x)\to (b,2x+c) \to (a,4x+3c)\),\(c\)为\(g\)的倍数,在对\(\gcd(3g,MOD)\)取模之后,就变成了\((a,4x)\)。

因此\(p\)只需要记录它的奇偶性。因此取值范围为\(\{0,1\}\)。

总共有\(6n\)种状态,连边,并查集维护。

在查询的时候,相当于从\((T,z)\)出发到\((S,R+z)\)

询问是否存在\(p,q\)使得\(R+z\equiv 2^{2k+p}z+qg \pmod {\gcd(3g,MOD)},k\in Z\)

预处理能表示为\(2^{2k+p}z\)的点有哪些,然后就可以快速判断了。


using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
int gcd(int a,int b){
	while (b){
		int k=a%b;
		a=b,b=k;
	}
	return a;
}
int n,m,p;
struct EDGE{
	int to,c;
	EDGE *las;
} e[N*2];
int ne;
EDGE *last[N];
void link(int u,int v,int c){
	e[ne]=(EDGE){v,c,last[u]};
	last[u]=e+ne++;
}
int g,d,z;
int pz[2][1000010];
struct Dsu{
	Dsu *p;
	Dsu *getfa(){return p==this?p:p=p->getfa();}
} *f[N][2][3];
bool check(int S,int T,int R){
	for (int j=0;j<2;++j)
		for (int k=0;k<3;++k){
			int t=((z+R-k*g)%d+d)%d;
			if (pz[j][t] && f[T][0][0]->getfa()==f[S][j][k]->getfa())
				return 1;			
		}
	return 0;
}
int main(){
	int Q;
	scanf("%d%d%d%d",&n,&m,&Q,&p);
	for (int i=1;i<=m;++i){
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		link(u,v,c),link(v,u,c);
	}
	g=p;
	for (int i=1;i<=n;++i){
		int c1=last[i]->c;
		for (EDGE *ei=last[i]->las;ei;ei=ei->las)
			g=gcd(g,gcd((c1-ei->c+p)%p,(ei->c-c1+p)%p));
	}
	d=gcd(3*g,p);
	z=last[1]->c%g;
	for (int i=1;i<=n;++i)
		for (EDGE *ei=last[i]->las;ei;ei=ei->las)
			ei->c-=z;
	for (int i=1;i<=n;++i)
		for (int j=0;j<2;++j)
			for (int k=0;k<3;++k){
				f[i][j][k]=new Dsu;
				f[i][j][k]->p=f[i][j][k];
			}
	pz[0][z]=1;
	pz[1][z*2%d]=1;
	if (z){
		for (int x=z*4%d;x!=z;x=x*4%d)
			pz[0][x]=1;
		for (int x=z*8%d;x!=z*2%d;x=x*4%d)
			pz[1][x]=1;
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<2;++j)
			for (int k=0;k<3;++k)
				for (EDGE *ei=last[i];ei;ei=ei->las){
					int j_=(j+1)%2,k_=(k*2+ei->c/g)%(d/g);
					f[ei->to][j_][k_]->getfa()->p=f[i][j][k]->getfa();
				}
	while (Q--){
		int S,T,R;
		scanf("%d%d%d",&S,&T,&R);
		if (check(S,T,R))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
上一篇:简述EI电离源的工作原理


下一篇:活动选择-贪心