Atcoder agc031F

真神题，对着题解想了一天才想明白。具体题解租酥雨的博客写得很好了。这里可能就是复述了一遍他的题解。
考虑倒着做，每次就是把当前和$\ast 2$再加上当前边的权值。把在点$x$且和为$c$的状态称作$(x,c)$，即问从$(T,0)$能否到达$(S,R)$。先注意到状态之间的转移是可逆的（来回走一条边即可），那么只用判断连通性。
再注意到如果点$x$有两条边权为$u$和$v$的出边，不妨设分别到点$u^{\prime }$和$v^{\prime }$，我们就可以由$(x,c)\simeq (u^{\prime },2c+u)\simeq (x,4c+3u)$与$(x,c)\simeq (v^{\prime },2c+v)\simeq (x,4c+3v)$推出$(x,c)\simeq (x,c+3(u-v))$。进一步的可以推出某个点两个和差图中任意两条边边权差的$3$倍的状态都是等价的。不妨设图中任意两条边边权差的$\gcd$为$g$，那么可以将$MOD$变为$\gcd (MOD,3g)$。
现在可能的状态数还是很大，不过我们发现任意两条边边权$\mathrm{m}\mathrm{o}\mathrm{d}g$都是相等的，将它设为$z$，那么每条边的权值在$\mathrm{m}\mathrm{o}\mathrm{d}MOD$意义下为 p g + z ( p ∈ { 0 , 1 , 2 } ) pg+z(p in {0,1,2}) pg+z(p∈{0,1,2})。如果我们将和在$\mathrm{m}\mathrm{o}\mathrm{d}MOD$意义下加$z$，每条边边权在$\mathrm{m}\mathrm{o}\mathrm{d}MOD$意义下减$z$，可以发现操作是不变的（$(x,c)\simeq (u,2c+(pg+z))$变为$(x,c+z)\simeq (u,2(c+z)+((pg+z)-z)$）。这样的话经过$d$步后，$(x,c)$只会变成 ( u , 2 d c + p g ) ( p ∈ { 0 , 1 , 2 } ) (u,2^dc+pg)(p in { 0,1,2}) (u,2dc+pg)(p∈{0,1,2})，并且我们来回走一条边的话，$p$不变，$d$会加$2$，于是可以将$d$变为$d\mathrm{m}\mathrm{o}\mathrm{d}2$。
这样就只有$6n$个状态了，直接并查集预处理连通性即可。询问的时候即为查询是否有$(T,z)\simeq (S,R+z)$，预处理每个数是否在$\mathrm{m}\mathrm{o}\mathrm{d}MOD$意义下是否是$2$的奇/偶次幂，就可以暴力枚举几种情况判定了。
时间复杂度$\mathcal{O}((n+m+q)\alpha (n))$。

#include <bits/stdc++.h>
#define last last2
#define FR first
#define SE second

using namespace std;

typedef pair<int,int> pr;

namespace SETS {

int fa[300005];

void init(int n) {
  for(int i=1;i<=n;i++) fa[i]=i;
}

int find_father(int x) {
  return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}

bool check(int x,int y) {
  x=find_father(x);y=find_father(y);
  return x==y;
}

void merge(int x,int y) {
  x=find_father(x);y=find_father(y);
  if (x==y) return;
  fa[x]=y;
}

}

inline int id(int x,int y,int z) {
  return (x-1)*6+y*2+z+1;
}

vector <pr> e[50005];

bool vis[2][1000005];

void pre(int s,int mod) {
  for(int i=0,j=s;i<(mod<<1);i++,j=j*2%mod)
    vis[i&1][j]=1;
}

int main() {
  int n,m,k,mod;
  scanf("%d%d%d%d",&n,&m,&k,&mod);
  int g=0,last=-1;
  for(int i=1;i<=m;i++) {
  	int x,y,z;
  	scanf("%d%d%d",&x,&y,&z);
  	e[x].push_back(pr(y,z));
  	e[y].push_back(pr(x,z));
  	if (last!=-1) g=__gcd(g,abs(z-last)); 
  	last=z;
  }
  if (!g) g=mod;
  mod=__gcd(mod,3*g);
  int v=e[1][0].SE%g;
  pre(v,mod);
  SETS::init(6*n);
  for(int i=1;i<=n;i++)
    for(int j=0;j<e[i].size();j++) {
    	int u=e[i][j].FR,v=e[i][j].SE/g;
    	for(int k=0;k<3;k++) {
    		SETS::merge(id(i,k,0),id(u,(2*k+v)%3,1));
    		SETS::merge(id(i,k,1),id(u,(2*k+v)%3,0));
		}
	}
  for(int i=1;i<=k;i++) {
  	int x,y,z;
  	scanf("%d%d%d",&x,&y,&z);
  	z=(z+v)%mod;
  	bool ok=0;
  	for(int j=0;j<3;j++)
  	  for(int k=0;k<2;k++)
  	    if (SETS::check(id(y,0,0),id(x,j,k))&&vis[k][(z-j*g%mod+mod)%mod]) ok=1;
  	puts((ok)?"YES":"NO");
  }
  return 0;
}

最后

以上就是美好书本为你收集整理的Atcoder agc031F的全部内容，希望文章能够帮你解决Atcoder agc031F所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。