The 2024 ICPC Asia East Continent Online Contest (I) C. Permutation Counting 4（二分图完美匹配奇偶 模拟高斯消元/并查集）

题目

每次给定n(n<=1e6)，有n个限制，

第i个限制是(li,ri)，要求第i个数位于[li,ri]之间

问有多少排列同时满足n个限制，答案对2取模，也就是只需要知道奇偶性即可

实际t(t<=1e6)组样例，保证sumn不超过1e6

思路来源

菜菜园子群+daydreamers群

题解

首先，问题转化成二分图的完美匹配计数问题

左边点[1，n]，右边点[1，n]，左边点i向右边点[li，ri]里的每个点连边，问有多少种完美匹配

这个东西可以用积和式求，矩阵的构造方法是a[i][j]=1（如果左i和右j之间有边），否则为0

根据积和式的定义，

这个就是n行n列里选n个1出来，任意两个数不在同一行同一列，n!种方案都求和的值

而根据行列式的定义，n行n列里选n个1出来，任意两个数不在同一行同一列，

对于这n!种方案，其中逆序对为奇数的排列是减，逆序对为偶数的排列是加

而每项要么是1要么是0，所以这俩东西模2的值是相同的

01矩阵（F2上的矩阵/全幺模矩阵）里行列式的值只可能是0，-1，1三种情况，

F2即只有0和1的域（mod 2的域）

线性相关（秩为0）时行列式值是0，单位矩阵E的行列式值是1，给1的两行换一换行列式是-1

所以，问题等价于判断矩阵对应的行列式的值是否为0，即是否线性相关

做法是对于每个[l,r]，连边l-1和r，如果出现环，说明线性相关，否则线性无关

因为矩阵里每行的1是连续的，可以理解成前缀和，

出现一个[l,r]的一行时，连边l-1和r，说明矩阵里有一行是表示sum[r] -sum[l-1]=r-l+1的

此时如果连边有环（或者用并查集维护时已经在一个连通分量里了），

表示本次描述的这个前缀和关系已经可以被之前的行表示出来了，也就是线性相关了

比如，[1，2]、[3，3]、[1，3]，三个中知道任两个，自然能推第三个，

这对应了前缀和的作和、作差，也对应了高斯消元消去其他行的线性变换操作，二者在此刻等价

代码

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<array>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=1e6+10;
int t,n,u,v,par[N];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
bool mer(int u,int v){
    u=find(u),v=find(v);
    if(u==v)return 1;
    par[v]=u;
    return 0;
}
int main(){
    sci(t);
    while(t--){
        sci(n);
        rep(i,0,n)par[i]=i;
        bool ok=0;
        rep(i,1,n){
            sci(u),sci(v);
            ok|=mer(u-1,v);
        }
        puts(ok?"0":"1");
    }
    return 0;
}

Bonus

每次给定n(n<=1e6)，有n个限制，

第i个限制是(li,ri)，要求第i个数位于[li,ri]之间

问在同时满足n个限制的排列中，逆序对为奇数的排列更多还是逆序对为偶数的排列更多

Solution

行列式有两个定义，一个是逆序对排列数的，一个是代数余子式的，

这里还是用逆序对排列数这个定义，所以就是求矩阵的行列式的值，

行列式=偶-奇，行列式的值只可能是-1,0,1，看下符号就可以了

这里需要模拟高斯消元，暴力的方法是O(n^2)的，考虑用可并堆加速这个过程，变为O(nlogn)

把所有这个区间，按照L从小到大排序后，

可能会有若干L相同的区间，不妨有y个，类似于 [l,r1] [l,r2]，...，

这里只保留那个最小的r，不妨记为x，

对于同行的其他区间，都减去[l,x]这个区间作消去即可，

消去之后的区间是以x+1开头的，把这剩下的y-1个区间都塞进x+1那行里即可

1. 要维护每个 l 对应的 r

2. 要支持查询相同 l 的最小 r

3. pop出一个最小的元素

4. 把剩下所有区间的 l 同时快速合并进x+1内

所以，用可并堆加速第四步

代码

代码来自gyh佬

#include<bits/stdc++.h>
#define re register
using namespace std;
const int Mxdt=100000;	//���δ�С 
inline char gc(){
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	re int t=0;re char v=gc();
	while(v<'0')v=gc();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
	return t;
}
int rt[100002],ls[100002],rs[100002],v[100002],n,m,k,d[100002],pos[100002],p[100002];
inline int merge(re int x,re int y){
	if(!x||!y)return x+y;
	if(v[x]>v[y])swap(x,y);
	rs[x]=merge(rs[x],y);
	if(d[rs[x]]>d[ls[x]])swap(ls[x],rs[x]);
	d[x]=rs[x]?d[rs[x]]+1:0;
	return x;
}
int main(){
	int t=read();
	while(t--){
		n=read(),m=0;
		for(re int i=1;i<=n;++i)rt[i]=0;
		for(re int i=1;i<=n;++i){
			re int x=read();v[i]=read();
			p[i]=pos[i]=i,d[i]=ls[i]=rs[i]=0,rt[x]=merge(rt[x],i);
		}
		re bool ia=0;
		for(re int i=1;i<=n;++i){
			if(!rt[i]){ia=1;break;}
			re int x=rt[i],y=p[i];
			if(x^y)m^=1,swap(pos[x],pos[y]),p[pos[x]]=x,p[pos[y]]=y;
			rt[i]=merge(ls[rt[i]],rs[rt[i]]);
			if(v[rt[i]]==v[x]){ia=1;break;}
			if(v[x]<=n)rt[v[x]+1]=merge(rt[v[x]+1],rt[i]);
		}
		if(ia)puts("D");
		else if(m)puts("F");
		else puts("Y");
	}
}