题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1327
看博客：https://www.cnblogs.com/Narh/p/9791875.html
思路就是按列DP，如果不是必须填就先空下这一列，记录一下目前有多少可用的空列，遇到一个 l 的结束时就从中选一些列放上棋子，并乘个排列；
对于 r，方案数在当前列体现，所以要记录当前列可填的位置；
注意别漏了状态，当前可转移的状态是填 l，填 r，不填，填在不是 l 也不是 r 的地方四种转移；
还有各种细节...全仰仗 Narh 提点；
呆滞了半小时...一对拍就发现...在算 A 的地方别忘了写 (ll) !!!
好题啊！
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int const xn=55,xm=205,mod=1e9+7; int n,m,l[xn],r[xn],f[xm][xm][xm],jc[xm],jcn[xm],sl[xm],sr[xm]; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return f?ret:-ret; } ll pw(ll a,int b) { ll ret=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1)ret=(ret*a)%mod; return ret; } void init() { jc[0]=1; for(int i=1;i<=m;i++)jc[i]=((ll)jc[i-1]*i)%mod; jcn[m]=pw(jc[m],mod-2); for(int i=m-1;i>=0;i--)jcn[i]=((ll)jcn[i+1]*(i+1))%mod; } int A(int n,int m){return (ll)jc[n]*jcn[n-m]%mod;}//(ll)!!! void upt(int &x,int y){x+=y; while(x>=mod)x-=mod; while(x<0)x+=mod;} int main() { n=rd(); m=rd(); init(); for(int i=1;i<=n;i++)l[i]=rd(),r[i]=rd(),sl[l[i]]++,sr[m-r[i]+1]++; for(int i=1;i<=m;i++)sr[i]+=sr[i-1]; f[0][0][0]=1; for(int i=0,num=0;i<m;i++,num=num+sl[i])//列 for(int j=max(0,sl[i+1]-1);j<=i-num;j++)//剩余 for(int k=0;k<=min(i,n);k++)//填r { if(!f[i][j][k])continue; if(sl[i+1]) upt(f[i+1][j+1-sl[i+1]][k],(ll)f[i][j][k]*A(j+1,sl[i+1])%mod); //,printf("f[%d][%d][%d]=%d A(%d,%d)=%lld f[%d][%d][%d]=%d ",i,j,k,f[i][j][k],j+1,sl[i+1],A(j+1,sl[i+1]),i+1,j+1-sl[i+1],k,f[i+1][j+1-sl[i+1]][k]);//l else upt(f[i+1][j+1][k],f[i][j][k]);//0 if(sr[i+1]>k&&j>=sl[i+1]) upt(f[i+1][j-sl[i+1]][k+1],(ll)f[i][j][k]*A(j,sl[i+1])%mod*(sr[i+1]-k)%mod); //,printf("sr=%d k=%d f[%d][%d][%d]=%d f[%d][%d][%d]=%d ",sr[i+1],k,i,j,k,f[i][j][k],i+1,j-sl[i+1],k+1,f[i+1][j-sl[i+1]][k+1]);//r(+l) if(num-sr[i+1]&&j>=sl[i+1]) upt(f[i+1][j-sl[i+1]][k],(ll)f[i][j][k]*A(j,sl[i+1])%mod*(num-sr[i+1])%mod); //,printf("!l!r:f[%d][%d][%d]=%d A=%lld k=%d f[%d][%d][%d]=%d ",i,j,k,f[i][j][k],A(j,sl[i+1]),num-sr[i+1],i+1,j-sl[i+1],k,f[i+1][j-sl[i+1]][k]);//!l,!r (+l) // printf("f[%d][%d][%d]=%d ",i,j,k,f[i][j][k]); } int ans=0; for(int j=0;j<=m-2*n;j++)upt(ans,f[m][j][n]); //,printf("f[%d][%d][%d]=%d ",m,j,n,f[m][j][n]); printf("%d ",ans); return 0; }