如何评价 2024 ICPC Asia EC 网络预选赛（第一场）？
神经坐牢场 ICPC
好像这个 C 是原题，然后榜被人带偏了，我们队一整场都没想出来。真服了。
这种题不会就是不会，一点机会都没有。
行列式的妙用 | ShwBlog题目大意
给定 个区间
，求有多少个
的排列
满足
。输出答案
的结果。
思路分析
还是很妙的。我们根据限制条件构造矩阵 ，使得：
。要求的答案如下：
其中 为所有排列。其实就是枚举排列判断是否合法。
这个定义是不是看着很像行列式？行列式完全展开如下：
只是去掉了正负号而已。事实上，要求的式子被称为积和式（permanent），记作 。由于只是去掉了正负号，不难发现：
进一步地，模二意义下行列式是否为 0，实际上是判断矩阵在模二意义下是否可逆，即检查是否有向量能被其他向量在模二意义下线性表出。
此时，区间的条件发挥了性质。我们可以建出一张 个点的图，对于区间
，将
与
连边。如果在图上
之间可达，说明通过向量模二意义下的线性运算，可以产生一个
的区间。
这样，我们用一个并查集维护可达性，每次加边之前判断：如果 已经可达，说明区间
已经可以被线性表出，那么答案是 0。如果所有区间都不可被表出，那么答案是 1。
#include <bits/stdc++.h>
using namespace std;
const int MAXN(1e6 + 5);
int n;
int f[MAXN];
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n + 1; i++) {
f[i] = i;
}
int ans = 1;
for (int i = 1; i <= n; i++) {
int l, r; scanf("%d %d", &l, &r);
l = find(l); r = find(r + 1);
if (l != r) f[r] = l;
else ans = 0;
}
printf("%d\n", ans);
}
int main() {
int _;
scanf("%d", &_);
while (_--) {
solve();
}
return 0;
}
新公网安备 65010402001845号