题目翻译
题目给我们一个长度为n的排列，代表n行沙子，其元素大小就是第i行沙子的长度。题目还给我们一个长度为n的数组，其数组元素的值代表第i行沙子的颜色。最终沙子会因重力而落下，我们要计算初始有多少种排列和颜色的组合可以使得最终沙子落下来的效果与给定的一样，注意对998244353取模。
思路
首先我们通过观察发现本题的一个重要性质，数组的颜色数组是不会发生改变的，因为每一行的沙子的长度都大于等于1。所以第一格的元素的颜色就把整个数组的颜色给定了下来。并且长度为i的沙子是什么颜色也不会改变，所以方案数会增多就来源于同色的沙子之间的交换。我们发现对于颜色相同的第x行和第y行沙子可以交换的条件是沙子x和y之间不存在比其长度最小值大的异色沙子行，我们可以使用并查集和链表，从长度最小的沙子行开始考虑交换维护这个过程计算答案。
注意这里有一个误区，用并查集从小到大合并之后阶乘计算贡献是错误的，其并不可以保证我们的交换条件合法。
代码
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
| struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
constexpr ll mod = 998244353;
void solve(){
int n;
std::cin >> n;
std::vector<int> len(n + 1, 0);
std::vector<int> col(n + 2, 0);
for(int i = 1; i <= n; i++)
std::cin >> len[i];
for(int i = 1; i <= n; i++)
std::cin >> col[i];
auto dsu = DSU(n + 1);
std::vector<int> L(n + 2, 0);
std::vector<int> R(n + 2, 0);
for(int i = 1; i <= n; i++){
if(col[i] == col[i - 1])
dsu.merge(i, i - 1);
L[i] = i - 1;
R[i] = i + 1;
}
std::vector<int> op(n, 0);
for(int i = 0; i < n; i++)
op[i] = i + 1;
std::sort(op.begin(), op.end(), [&](int a, int b){
return len[a] < len[b];
});
ll ans = 1;
for(auto pos : op){
ans = (ans * dsu.size(pos)) % mod;
dsu.siz[dsu.find(pos)] -= 1;
if(dsu.size(pos) == 0)
if(col[L[pos]] == col[R[pos]] && col[R[pos]] != 0)
dsu.merge(L[pos], R[pos]);
R[L[pos]] = R[pos];
L[R[pos]] = L[pos];
}
std::cout << ans << endl;
}
|
