题目描述
Unputdownable 手中有一个长度为 的排列 。
他在练习单调栈的时候用程序对于每一个 求出了最大的 使得 且 ，以及最小的 使得 且 。
特别的，若这样的 不存在，则定义为 ，不存在的 则定义为 。
某日 Unputdownable 忘记了排列 ，而且只剩余分别重排后的 和 数组了，你能帮助他还原原来的排列 吗？
随后由于他发现无法还原 ，你只要告诉他有多少种可能的原排列 。
答案对于 取模，数据保证至少存在一种方案。
输入格式
第一行输入一个整数 。
第二行输入 个整数，表示重排后的 。
第三行输入 个整数，表示重排后的 。
输出格式
输出一行，包含一个整数，表示可能的排列数量对 取模后的值。
SAMPLE I/O
I
O
数据范围
对于 的数据，，，数据保证至少存在一种方案。
思路
转换为正常的 l 序列和 r 序列
这里题目提供了乱序的 序列和 序列，我们看他很不顺眼，想把它转换成正常的 和 序列。怎么转换呢？
想想 和 序列的定义。 指的是 左边离 最近的小于 的数。
回顾正常构建 序列的步骤（）：
我们现在有一个栈和一个排列 ，从左往右扫序列 ，扫到第 个数，就检查一下栈顶：若栈顶的数 比 小，那么就说明 找到第一个比它小的数了。把 插入栈。否则说明比 小的数还在栈的下面。
同时，我们也发现了 的 也找到了，就是 。因为这时 比栈顶的数小。而 的 在之前确定了（因为 不可能跑到 的右边去），所以 的 和 都找到了，就把 pop 出栈，以便 和后面的数确定 值。
（图为正常的求解L和R序列的图解）
于是我们可以发现，一个数的位置 前面有多少个比它大的数，那么 序列里面就会有多少个 。相应的， 后面又多少个比他大的数，那么 序列里面就会有多少个 。我们可以根据这个性质来重新建立起正确的 和 序列。
这里不用管他的数值，只用管他的下标（就是上图里的紫色数值）。记录 和 序列里的每个数出现的次数 和 ，然后根据出现次数倒推。
例如：假设现在扫到了 ， ，那么就先往栈里删除两个数，记录这两个数的 值为 ，然后再把 压入栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| for(int i=1;i<=n;i++)
cin>>tmp, cntl[tmp] ++;
for(int i=1;i<=n;i++)
cin>>tmp, cntr[tmp] ++;
for(int i=1;i<=n+1;i++){
for(int j=1;j<=cntr[i];j++){
r[st[len]] = i;
len--;
}
st[++len] = i;
}
len = 0;
for(int i=n;i>=0;i--){
for(int j=1;j<=cntl[i];j++){
l[st[len]] = i;
len--;
}
st[++len] = i;
}
|
将序列转换为 DAG（有向无环图）
我们回到定义， 序列和 序列的意义是什么？是分别在左边（）和右边（）第一个比他小的数。那就说明，我们构建出的序列必须要满足 ，和 的关系。
这种限制可以转化成一条有向边，有 的限制就只需要从 向 连一条有向边即可。于是我们就得到了一个有向无环图。为什么无环？因为不存在 且 的关系。
建成了一个有向无环图之后，为了满足这种关系，可以从最小的数，就是入度为 的点开始赋最小值，然后依次往里扩散，赋的值也相应的比之前大。发现这种方法是不是非常像求拓扑序？于是这道题的目标就变成了：给一个 DAG，求他的拓扑序计数。
转图为树
对于普通图的拓扑序计数，他的复杂度是很大的，放到这道题是不现实的。我们再回到图上，发现原来的图他的边太多而且太复杂了！，用一般的图或者 DAG 拓扑序计数非常容易炸。想想怎么简化这张图。
我们发现，对于一个点 的 到 的区间，除了下标为 和 的点，其他的数都是大于等于 的。并且 和 都是小于 的，于是 和 双方都很有可能成为对方的 或 。
只有两种情况：
- 若，也是 ，那么就说明 是 左边第一个小于点 的点，于是 肯定会向 连边。那么就只需 向 连边。
- 否则，，也是 ，那么就说明 是 右边第一个小于点 的点，于是 肯定会向 连边。那么就只需 向 连边。
但是，要特判：如果 ，就只能 向 连边；如果 ，就只能 向 连边。
于是，从每一个点都伸出来了一条边，这样就有 条边，但是最小值的 ，就相当于是向虚空连边，真实存在的边只有 条。 个点， 条边，每条边都有度数……
它是一棵树！
一棵树求拓扑序计数
对于一棵树，我们要求他的拓扑序计数：
为了更好的拓扑序计数，我们把以前的限制一改：
当 时， 向 连边。
我们已知一棵大小为 的树，如何求它的拓扑序计数？
现在先不管合不合法，把每个拓扑序分配给每一个点，那么一共就有 种情况。其中只考虑这个根，让根满足条件的就是根节点的拓扑序小于其他所有节点，就是 。
枚举这 种情况，其中 只能在第一个位置。其他的位置都不合法。那么这个概率就是 。然后再递归下去，求出每个节点的合法概率。把这些点的概率相乘，就变成了总的合法概率。再乘上总共情况 ，即为总共合法情况数：
然后用类似拓扑排序的算法求出他的 积，最后让 除以它即得到答案。
Code
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
89
90
91
92
93
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e6+6;
int cntl[N], cntr[N];
int n;
int tmp;
int l[N], r[N];
int st[N], len;
struct node{
int fa, siz, deg;
}tr[N];
queue<int>q;
typedef long long ll;
const ll mod = 998244353;
ll ksm(ll bas, ll x){
ll ans = 1;
while(x){
if(x&1) ans = ans * bas % mod;
bas = bas * bas % mod;
x >>= 1;
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>tmp;
cntl[tmp] ++;
}
for(int i=1;i<=n;i++){
cin>>tmp;
cntr[tmp] ++;
}
for(int i=1;i<=n+1;i++){
for(int j=1;j<=cntr[i];j++){
r[st[len]] = i;
len--;
}
st[++len] = i;
}
len = 0;
for(int i=n;i>=0;i--){
for(int j=1;j<=cntl[i];j++){
l[st[len]] = i;
len--;
}
st[++len] = i;
}
for(int i=1;i<=n;i++){
if(l[i] == 0){
tr[i].fa = r[i];
tr[r[i]].deg ++;
}else if(r[i] == n+1){
tr[i].fa = l[i];
tr[l[i]].deg ++;
}else if(r[l[i]] != r[i]){
tr[i].fa = r[i];
tr[r[i]].deg ++;
}else{
tr[i].fa = l[i];
tr[l[i]].deg ++;
}
}
for(int i=1;i<=n;i++){
if(tr[i].deg == 0) q.push(i);
}
ll sizpi = 1;
while(!q.empty()){
int u = q.front();
q.pop();
tr[u].siz ++;
(sizpi *= (tr[u].siz)) %= mod;
if(tr[u].fa == 0 || tr[u].fa == n+1) continue;
tr[tr[u].fa].siz += tr[u].siz;
tr[tr[u].fa].deg --;
if(tr[tr[u].fa].deg == 0){
q.push(tr[u].fa);
}
}
ll factn = 1;
for(int i=1;i<=n;i++){
factn = factn * i % mod;
}
cout<<factn*ksm(sizpi, mod-2)%mod<<'\n';
return 0;
}
|
