用欧拉路径判断图同构推出reverse合法性：1116T4

http://cplusoj.com/d/senior/p/SS231116D

假设我们要把 $a$ 变成 $b$，我们在 $a_i$ 和 $a_{i+1}$ 之间连边，$b$ 同理，则 $a$ 能变成 $b$ 的充要条件是两图 $A,B$ 同构。

必要性显然，因为无论如何reverse都不会改变图的形态。我们现在要证明的是图的任意欧拉路径都可以通过reverse构造出来。

考虑第一个 $a_i\ne b_i$ 的位置 $i$，设 $x=b_i,y=b_{i-1}=a_{i-1}$。在图同构是必然存在一个 $a_k=x$，且 $a_{k-1}$ 或 $a_{k+1}$ 其中一个等于 $y$。（注意 $A,B$ 同构）

如果 $a_{k+1}=y$，我们直接reverse即可。如果 $a_{k-1}=y$，我们只需要考虑 $(x,y)$ 这条边在 $A$ 中是不是桥就行。因为在 $B$ 中一定不是桥（注意到 $y$ 必然出现两次）

因为如果在 $A$ 中是桥，$B$ 中不是，说明 $A,B$ 不同构，和我们的前提冲突。

如果在 $A$ 中不是桥，说明对于这条边来说 $A,B$ 同构，说明一定存在 $i\le l\le k-1,r>k+1$ 满足 $a_l=a_r$。我们直接按 $[l,r]$ reverse即可。因此一定可以构造

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>using 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 S=5000005;
#define pb push_back
#define fi first
#define se secondint n, a[S], t[S], k, i, tot;
bool b[S]; 
int ans[S];
vector<pair<int, int> >G[S]; void dfs(int x) {for(; t[x]<G[x].size(); ){auto p=G[x][t[x]]; ++t[x]; if(b[p.se]) continue; int y=p.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(t==0) for(int i=1;i<=n;i++) scanf("%d",&a[i]);else{int ra;scanf("%d%llu%llu",&ra,&rnd.k1,&rnd.k2);for(int i=1;i<=n;i++) a[i]=rnd.gen(ra)+1;}//	cun(n+1, a[1]); cun(n+2, a[n]); for(i=1; i<n; ++i) cun(a[i], a[i+1]); for(i=1; i<=n+2; ++i) {sort(G[i].begin(), G[i].end()); 
//		reverse(G[i].begin(), G[i].end()); }dfs(a[1]); reverse(ans+1, ans+n+1); /*code here*/if(t==0){for(int i=1;i<=n;i++) printf("%d ",ans[i]);printf("\n");}else{int bse=1919839,p=1000000007;int mul=1,res=0;for(int i=1;i<=n;i++,mul=1ll*mul*bse%p) res=(res+1ll*ans[i]*mul%p)%p;printf("%d\n",res);}return 0;
}