CF2022E1/E2题解这道题当我们知道了一行以及一列的元素之后就可以确定一整个矩阵我们不妨令知道的数字为第一行第一列那么对于任何一个点 a[i,j]v 我们都可以得到a[1,i]^a[j,1]v;因此我们可以看作nm-1个节点在图上对于每一个已知的点都会建立一条i-j的为v的约束对于easy版本 这个约束是否满足我们可以用dfs维护pre[u]表示u到连通块根节点的距离那么对于uv就有pre[v]^pre[u]就是二者之间的约束也就是路径异或dfs的判断从根节点开始遍历如果遇到没遍历过的边那么就是树边遍历下去如果遍历过 那么就是回边生成一个环此时我们需要判断这个回边的边权是否等于二者的路径异或不相等就pass对于hard版本涉及到动态加点所以我们要用带权并查集实现异或约束的判断我们维护d[x]表示节点x到连通块根节点的异或路径最终的结果若得到了k个连通块每个连通块内部的根节点一旦确定 整个连通块就确定了因此一个连通块就要乘2^30 也就是(230)k 但是当所有的x和y同时异或一个值的时候总的值不变 去掉这个重复的情况也就是(230)K-1E1 codeDFS:#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod1e97;intpows[200005];voidsolve(){intn,m,k,q;cinnmkq;vectorvectorpairint,inte(n1m);for(inti1;ik;i){intl,r,v;cinlrv;e[l].emplace_back(rn,v);e[rn].emplace_back(l,v);}vectorintpref(n1m,-1);boolok1;intcnt0;autodfs[](autoself,intu)-void{for(auto[v,w]:e[u]){if(pref[v]-1){pref[v]pref[u]^w;self(self,v);}else{if((pref[v]^pref[u])!w){ok0;}}}};for(inti1;inm;i){if(pref[i]!-1)continue;else{cnt;pref[i]0;dfs(dfs,i);}}if(ok){coutpows[cnt-1]\n;}else{cout0\n;}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);pows[0]1;for(inti1;i200005;i){pows[i](pows[i-1]*((130)%mod))%mod;}intt1;cint;while(t--)solve();return0;}E2 code:带权并查集#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod1e97;intpows[200005];boolok1;structDSU{vectorintfa,sz;DSU(){}DSU(intn){init(n);}voidinit(intn){fa.resize(n1);iota(fa.begin(),fa.end(),0);sz.assign(n1,0);}intfind(intx){if(xfa[x])returnx;else{intffind(fa[x]);sz[x]^sz[fa[x]];returnfa[x]f;}}boolmerge(intx,inty,intw){intnxfind(x),nyfind(y);if(nxny){if((sz[x]^sz[y])!w){ok0;}return0;}// if (sz[x] sz[y]) swap(x, y);sz[ny]sz[x]^sz[y]^w;fa[ny]nx;return1;}};voidsolve(){ok1;intn,m,k,q;cinnmkq;DSUdsu(nm1);intcntnm;for(inti1;ik;i){intl,r,w;cinlrw;if(dsu.merge(l,rn,w))cnt--;}if(ok)coutpows[cnt-1]\n;elsecout0\n;for(inti1;iq;i){intl,r,w;cinlrw;if(dsu.merge(l,rn,w))cnt--;if(ok)coutpows[cnt-1]\n;elsecout0\n;}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);pows[0]1;for(inti1;i200005;i){pows[i](pows[i-1]*((130)%mod))%mod;}intt1;cint;while(t--)solve();return0;}