网上建站赚钱,网站推广策划案,重庆地产网站建设方案,网站优化助手http://cplusoj.com/d/senior/p/SS231116D
假设我们要把 a a a 变成 b b b#xff0c;我们在 a i a_i ai 和 a i 1 a_{i1} ai1 之间连边#xff0c; b b b 同理#xff0c;则 a a a 能变成 b b b 的充要条件是两图 A , B A,B A,B 同构。
必要性显然#xff0…http://cplusoj.com/d/senior/p/SS231116D
假设我们要把 a a a 变成 b b b我们在 a i a_i ai 和 a i 1 a_{i1} ai1 之间连边 b b b 同理则 a a a 能变成 b b b 的充要条件是两图 A , B A,B A,B 同构。
必要性显然因为无论如何reverse都不会改变图的形态。我们现在要证明的是图的任意欧拉路径都可以通过reverse构造出来。
考虑第一个 a i ≠ b i a_i\neq b_i aibi 的位置 i i i设 x b i , y b i − 1 a i − 1 xb_i,yb_{i-1}a_{i-1} xbi,ybi−1ai−1。在图同构是必然存在一个 a k x a_kx akx且 a k − 1 a_{k-1} ak−1 或 a k 1 a_{k1} ak1 其中一个等于 y y y。注意 A , B A,B A,B 同构
如果 a k 1 y a_{k1}y ak1y我们直接reverse即可。如果 a k − 1 y a_{k-1}y ak−1y我们只需要考虑 ( x , y ) (x,y) (x,y) 这条边在 A A A 中是不是桥就行。因为在 B B B 中一定不是桥注意到 y y y 必然出现两次
因为如果在 A A A 中是桥 B B B 中不是说明 A , B A,B A,B 不同构和我们的前提冲突。
如果在 A A A 中不是桥说明对于这条边来说 A , B A,B A,B 同构说明一定存在 i ≤ l ≤ k − 1 , r k 1 i\le l \le k-1,rk1 i≤l≤k−1,rk1 满足 a l a r a_la_r alar。我们直接按 [ l , r ] [l,r] [l,r] reverse即可。因此一定可以构造
#include iostream
#include algorithm
#include cstdio
#include vectorusing namespace std;struct xorShift128Plus {unsigned long long k1, k2;unsigned long long gen() {register unsigned long long k3 k1, k4 k2;k1 k4;k3 ^ k3 23;k2 k3 ^ k4 ^ (k3 17) ^ (k4 26);return k2 k4;}int gen(int w) {return gen()%w;}
}rnd;const int S5000005;
#define pb push_back
#define fi first
#define se secondint n, a[S], t[S], k, i, tot;
bool b[S];
int ans[S];
vectorpairint, int G[S]; void dfs(int x) {for(; t[x]G[x].size(); ){auto pG[x][t[x]]; t[x]; if(b[p.se]) continue; int yp.fi; b[p.se]1; dfs(y); }ans[tot]x;
}void cun(int x, int y) {G[x].pb({y, k}); G[y].pb({x, k});
}int main()
{freopen(life.in,r,stdin);freopen(life.out,w,stdout);#ifdef LOCALfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);#endifint t;scanf(%d%d,n,t);if(t0) for(int i1;in;i) scanf(%d,a[i]);else{int ra;scanf(%d%llu%llu,ra,rnd.k1,rnd.k2);for(int i1;in;i) a[i]rnd.gen(ra)1;}// cun(n1, a[1]); cun(n2, a[n]); for(i1; in; i) cun(a[i], a[i1]); for(i1; in2; i) {sort(G[i].begin(), G[i].end());
// reverse(G[i].begin(), G[i].end()); }dfs(a[1]); reverse(ans1, ansn1); /*code here*/if(t0){for(int i1;in;i) printf(%d ,ans[i]);printf(\n);}else{int bse1919839,p1000000007;int mul1,res0;for(int i1;in;i,mul1ll*mul*bse%p) res(res1ll*ans[i]*mul%p)%p;printf(%d\n,res);}return 0;
}
