题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5852
https://en.wikipedia.org/wiki/Lindström–Gessel–Viennot_lemma 行列式的sgn刚好是容斥系数 糖教说这个可以应用到区间图
所以直接建行列式然后做成对角线就可以了
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; char c; inline void read(int&a) { a=0;do c=getchar();while(c<'0'||c>'9'); while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar(); } const int Mod=1e9+7; int mul(int x,int y) { return x*1ll*y%Mod; } int add(int x,int y) { int res=x+y; if(res>=Mod)res-=Mod; if(res<0)res+=Mod; return res; } int Pow(int a,int x) { int res=1; for(;x;x>>=1,a=mul(a,a))if(x&1)res=mul(res,a); return res; } int Rev(int x) {return Pow(x,Mod-2);} const int MAXN=200; int A[MAXN][MAXN]; int Guess(int n) { int f=1,t=Mod-f; for(int i=1;i<=n;i++) { int r=-1; for(int j=i;j<=n;j++) if(A[j][i]){r=j;break;} if(r==-1)return 0; if(r!=i)swap(f,t); for(int j=i;j<=n;j++) swap(A[i][j],A[r][j]); for(int j=i+1;j<=n;j++) { int s=mul(A[j][i],Rev(A[i][i])); if(s) for(int k=i;k<=n;k++) A[j][k]=add(A[j][k],-mul(s,A[r][k])); } } int res=1; for(int i=1;i<=n;i++) res=mul(res,A[i][i]); return mul(res,f); } int Fact[200001],Re[200001]; int C(int x,int y) { if(x<y)return 0; return mul(mul(Fact[x],Re[x-y]),Re[y]); } int a[200001],b[200001]; int main() { Fact[0]=1; for(int i=1;i<=200000;i++)Fact[i]=mul(Fact[i-1],i); Re[200000]=Pow(Fact[200000],Mod-2); for(int i=199999;~i;i--)Re[i]=mul(Re[i+1],i+1); int T; read(T); while(T--) { int n,m; read(n),read(m); for(int i=1;i<=m;i++)read(a[i]); for(int i=1;i<=m;i++)read(b[i]); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) A[i][j]=C(b[j]-a[i]+n-1,n-1); int res=Guess(m); cout<<res<<endl; } return 0; }