2024ICPC网络赛第一场C. Permutation Counting 4（线性代数）
题目链接
题目大意：给你n个范围[ l i , r i l_i,r_i li,ri]，每个位置可以在这个范围中选择一个数，然后形成排列1到n的排列p。问p的所有情况的个数的奇偶性。
一个很妙的行列式转化，纯纯的线性代数。
首先，我们把p的总数表示出来。设矩阵
a
i
,
j
a_{i,j}
ai,j，表示的是第
i
个
i个
i个位置的是否可以表示
j
j
j。则p的所有可能为
∑
p
Π
i
=
1
n
a
i
,
P
i
\sum\limits_{p}\mathop{\Pi}\limits_{i=1}^{n}a_{i,Pi}
p∑i=1Πnai,Pi
其中p表示所有排列方式的总和。发现这是近似于矩阵a的行列式的值，不过去掉了其正负号。（在取模2的影响下，综合的加减没有影响）也就是说，只要我们求矩阵
a
a
a的行列式的值
m
o
d
2
mod\ 2
mod 2，就可以解出最终解。
根据矩阵的性质，矩阵的行列式
m
o
d
2
mod\ 2
mod 2为
0
0
0，等价于该矩阵
m
o
d
2
mod\ 2
mod 2下不可逆，也等价于该矩阵
m
o
d
2
mod\ 2
mod 2下的每一行的向量存在线性相关，也就是存在其中一个向量可以被其它向量表示。
至此，我们终于该题从看不懂的样子转化成了看起来像人话的子问题了。让我们解决这个子问题。每一个位置的向量[ l i , r i l_i,r_i li,ri]我们可以通过 r i − ( l i − 1 ) r_i-(l_{i}-1) ri−(li−1)表示，然后通过并查集判断出该向量能否通过其它向量表示。
int n,m;
int pre[1000005];
int find (int x){
if(pre[x]==x)return x;
else return pre[x]=find(pre[x]);
}
void icealsoheat(){
cin>>n;
for(int i=0;i<=n;i++)pre[i]=i;
int ans=1;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
l=find(l-1);
r=find(r);
if(l==r){
ans=0;
// break;
}
else{
pre[l]=r;
}
}
cout<<ans<<"\n";
}