C++(g++ 7.5.0) 解法, 执行用时: 28ms, 内存消耗: 8752K, 提交时间: 2022-10-25 11:31:07

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 100005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[500005],invjie[500005];
int C(int n,int m){return n>=m&&m>=0?jie[n]*invjie[m]%mod*invjie[n-m]%mod:0;}
void main_init(){
    int n=500000;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,k;
int a[300][300];
pii st[205],ed[205];
int get(){
	for(int i=1;i<=n;i++){
		if(a[i][i]==0){
			for(int j=i+1;j<=n;j++){
				if(a[j][i]){
					swap(a[i],a[j]);
					break;
				}
			}
			if(a[i][i]==0)return 0;
		}
		int d1=qpow(a[i][i]);
		for(int j=i+1;j<=n;j++){
			int d=d1*a[j][i]%mod;
			for(int k=i;k<=n;k++){
				a[j][k]=(a[j][k]+mod-d*a[i][k]%mod)%mod;
			}
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		(ans*=a[i][i])%=mod;
	}
	return ans;
}
int geta(int stx,int sty,int edx,int edy){
	int res=C(edx-stx+edy-sty,edx-stx);
	int nx=-2*k-1-stx,ny=1-sty;
	res-=C(edx-nx+edy-ny,edx-nx);
	nx=1-stx,ny=-2*k-1-sty;
	res-=C(edx-nx+edy-ny,edx-nx);
	return (res%mod+mod)%mod;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>st[i].first>>st[i].second>>ed[i].first>>ed[i].second;
	}
    sort(st+1,st+n+1);
    sort(ed+1,ed+n+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=geta(st[i].first,st[i].second,ed[j].first,ed[j].second);
		}
	}
	cout<<get();
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);
    int t=1;
    main_init();
    while (t--)
		solve();
}

C++(clang++ 11.0.1) 解法, 执行用时: 29ms, 内存消耗: 3884K, 提交时间: 2022-11-04 22:02:38

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
const int N=201;
int a[N][N];
int A[N],B[N];
int det(int n){
	int res=1,w=1;
	for(int i=1;i<=n;i++){ 
		for(int j=i+1;j<=n;++j){
    		while(a[i][i]){
     	    	int div=a[j][i]/a[i][i];
        		for(int k=i;k<=n;++k){
        		    a[j][k]=(a[j][k]-1ll*div*a[i][k]%mod+mod)%mod;
        		}
        		swap(a[i],a[j]);w=-w;
    		}
    		swap(a[i],a[j]);w=-w;
		}
	}
	for(int i=1;i<=n;i++)res=1ll*a[i][i]*res%mod;
	res=1ll*w*res;
	return (res+mod)%mod;
}

int qmi(int a,int n){
    int ans = 1;
    while(n){
        if(n & 1)ans = a * ans % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
const int M = 2e5 + 10;
int fac[M],invfac[M];
int cal(int n,int m){
    if(n < m || m < 0 || n < 0)return 0;
    return fac[n] * invfac[m] % mod * invfac[n-m] % mod;
}
struct node{
    int x,y;
    bool operator<(const node&C)const{
        return x < C.x;
    }
}s[202],e[202];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    fac[0] = 1;
    for(int i = 1; i < M; i ++ )fac[i] = fac[i-1] * i % mod;
    invfac[M-1] = qmi(fac[M-1],mod-2);
    for(int i = M-1; i; i -- ){
        invfac[i-1] = invfac[i] * i % mod;
    }
	cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        cin >> s[i].x >> s[i].y >> e[i].x >> e[i].y;
    }
    sort(s+1,s+1+n);
    sort(e+1,e+1+n);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(s[i].x + m <= e[j].y)a[i][j] = cal(2*m,e[j].x-s[i].x)-cal(2*m,e[j].x-s[i].y+m+1);
            else a[i][j] = cal(2*m,e[j].x-s[i].x)-cal(2*m,e[j].y-s[i].x+m+1);
        }
    }
	int ans=det(n);
    cout << ans << '\n';
}