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

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134444131

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

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

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

考虑第一个 ai≠bia_i\neq b_i 的位置 ii ，设 x=bi,y=bi−1=ai−1x=b_i,y=b_{i-1}=a_{i-1} 。在图同构是必然存在一个 ak=xa_k=x ，且 ak−1a_{k-1} 或 ak+1a_{k+1} 其中一个等于 yy 。（注意 A,BA,B 同构）

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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 second

int 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 LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	int 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;
}