【2023北京集训4】代数 做题记录

有一个 $n\times n$ 的矩阵，刚开始所有位置都为 $0$。

接下来进行 $n$ 次操作，第 $i$ 次会在左上角为 $(xl_i,yl_i)$，右下角为 $(xr_i,yr_i)$ 的矩形中等概率随机选择一个位置将其 $+1$。

求操作完后矩阵行列式的期望值，对 $10^9+7$ 取模。

$n\times n$ 的矩阵 $a$ 的行列式 $|a|=\sum\limits_{p\in S_n}(-1)^{\text{inv}(p)}\prod\limits_{i=1}^n a_{i,p_i}$，其中 $S_n$ 为 $n$ 的排列的集合，$\text{inv}(p)$ 为 $p$ 的逆序对个数。

$1\le n\le 10^5$。

首先转成计数，只需要最后乘上 $\frac{1}{\prod\limits_i(xr_i-xl_i+1)(yr_i-yl_i+1)}$ 即可。

设最终矩阵为 $a$，则不难发现由于 $\sum\limits_{i}\sum\limits_{j}a_{i,j}=n$，所以若两次操作加到了同一个位置则行列式为 $0$。

设第 $i$ 次加在了 $(x_i,y_i)$，设 $fx_{a,b}$ 和 $fy_{a,b}$ 分别表示 $a,b$ 是否在 $(i,x_i)$ 和 $(i,y_i)$ 意义上构成逆序对，则不难发现 $a,b$ 在 $(x_i,y_i)$ 意义上构成逆序对当且仅当 $fx_{a,b}\oplus fy_{a,b}=1$，而一个逆序对的贡献是 $\times(-1)$，所以两维可以独立做。

那么现在问题变为求 $\sum\limits_{p\in S_n}(-1)^{\text{inv}(p)}\prod\limits_{i}[p_i\in[l_i,r_i]]$。

不难发现，若存在 $p_i,p_j\in[l_i,r_i]\cap[l_j,r_j]$，则将 $p_i,p_j$ 交换会让逆序对个数改变 $1$，且交换后还合法，所以会互相抵消。

那么每次选择 $l_i$ 最小的区间中 $r_i$ 最小的那个 $i$，让 $p_i:=l_i$，再将所有 $l_j=l_i$ 的 $l_j$ 都变为 $r_i+1$，不难发现这样填出来的方案一定合法，且根据这个构造方法不难看出合法方案最多只有一种，所以有一个有趣的性质就是 $\left(\sum\limits_{p\in S_n}(-1)^{\text{inv}(p)}\prod\limits_{i}[p_i\in[l_i,r_i]]\right)\in\{-1,1\}$。

这个贪心用可并堆维护即可，时间复杂度 $O(n\log n)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=100005,p=1000000007;

template<typename T,int siz>
class LTree
{
	private:
		struct node
		{
			T val;
			int dist,ls,rs;
		}tr[siz];
		int tot;
		inline int nnde(T val)
		{
			tr[++tot]={val,1,0,0};
			return tot;
		}
		inline void upda(int u)
		{
			int &ls=tr[u].ls,&rs=tr[u].rs;
			if(tr[ls].dist>tr[rs].dist) swap(ls,rs);
			tr[u].dist=tr[ls].dist+1;
		}
		int merge(int x,int y)
		{
			if(x==0||y==0) return x+y;
			if(tr[x].val>tr[y].val) swap(x,y);
			tr[x].ls=merge(tr[x].ls,y);
			upda(x);
			return x;	
		}
	public:
		inline void clear()
		{
			tr[tot=0]=(node){T(),0,0,0};
		}
		inline void ins(int &rt,T x)
		{
			rt=merge(rt,nnde(x));
		}
		inline T top(int rt)
		{
			return tr[rt].val;
		}
		inline void pop(int &rt)
		{
			rt=merge(tr[rt].ls,tr[rt].rs);
		}
		inline void meg(int &x,int y)
		{
			x=merge(x,y);
		}
};

struct node
{
	int xl,xr,yl,yr;
}a[S];

int n;
LTree<pair<int,int>,S> tr;
int rt[S];
int rex[S],rey[S];
int b[S],c[S];

inline void add(int p,int x)
{
	for(int i=p;i<=n;i+=i&-i) c[i]+=x;
}

inline int que(int p)
{
	int res=0;
	for(int i=p;i>=1;i-=i&-i) res+=c[i];
	return res;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].xl,&a[i].xr,&a[i].yl,&a[i].yr);
	tr.clear();
	for(int i=1;i<=n;i++) rt[i]=0;
	for(int i=1;i<=n;i++) tr.ins(rt[a[i].xl],make_pair(a[i].xr,i));
//	for(int i=1;i<=n;i++)
//	{
//		printf("%d %d %d %d\n",a[i].xl,a[i].xr,a[i].yl,a[i].yr);
//		auto pre=tr.top(rt[i]);
//		printf("%d: %d\n",pre.second,pre.first); 
//	}
	for(int i=1;i<=n;i++)
	{
		auto pre=tr.top(rt[i]);
		tr.pop(rt[i]);
		int id=pre.second,r=pre.first;
		if(r<i) return puts("0"),void();
		rex[id]=i;
		tr.meg(rt[r+1],rt[i]);
	}
//	puts("FINX");
	tr.clear();
	for(int i=1;i<=n;i++) rt[i]=0;
	for(int i=1;i<=n;i++) tr.ins(rt[a[i].yl],make_pair(a[i].yr,i));
	for(int i=1;i<=n;i++)
	{
		auto pre=tr.top(rt[i]);
		tr.pop(rt[i]);
		int id=pre.second,r=pre.first;
		if(r<i) return puts("0"),void();
		rey[id]=i;
		tr.meg(rt[r+1],rt[i]);
	}
	for(int i=1;i<=n;i++) b[rex[i]]=rey[i];
	for(int i=1;i<=n;i++) c[i]=0;
	int res=1;
	for(int i=n;i>=1;i--)
	{
		res*=que(b[i]-1)&1?-1:1;
		add(b[i],1);
	}
	if(res<0) res+=p;
	for(int i=1;i<=n;i++)
	{
		int pre=1ll*(a[i].xr-a[i].xl+1)*(a[i].yr-a[i].yl+1)%p;
		res=1ll*res*qpow(pre,p-2)%p;
	}
	printf("%d\n",res);
}

int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}