(\)
(Description)
给出一张(N imes M)的棋盘，每个格子最多放置一个棋子，一个合法的放置方案需满足：
- 每列至多放置一个棋子
- 对于第(i)行，前(L_i)个格子中恰好只放一个，后(R_i)个格子中恰好只放一个
求合法方案数对(10^9+7)取模后的值。
- (Nin [1,50])，(Min [2,200])，(L_i,R_iin [1,M])，(L_i+R_ile M)
(\)
(Solution)
打死都想不到状态设计
注意到行之间无法记录以上各列状态直接转移，所以以列为状态。
考虑只有左边的限制：
- 设计(f[i][j])表示处理到前(i)列，还有(j)列未放置棋子的方案数。
- 考虑状态向后更新，每次做到第(i)列，统计左区间限制的右端点为下一列的行数(l_{i+1})，则下一列的这些限制都必须完成，因为这些行在哪一列被满足顺序无关，所以需要乘上排列，有(f[i+1][j+1-l_{i+1}]+=f[i][j] imes P_{ j}^{ l_{i+1}})
考虑只有右边的限制：
- 设计(f[i][k])表示处理到前(i)列，还有(k)行的限制未满足的方案数。
- 向后更新，但是需要同时统计右区间限制的左端点为下一列的行数(r_{i+1})和下一列不被右区间限制覆盖的行数(mid_{i+1})，考虑这一列放一个棋子放在上面那一种里，分情况讨论转移即可。
把它们合起来：
-
(f[i][j][k])表示处理到第(i)列，前面有(j)列还未放置棋子，还有(k)行未满足的方案数。
-
对于每一列(i)，统计左区间限制的右端点为当前列的行数(l_i)、右区间限制的左端点为当前列的行数(r_i)、当前列不被左右区间限制覆盖的行数(mid_i)。
-
同样每次到达左区间限制的右边界时，再考虑如何满足这些左区间，本列的放置考虑三种：
- 满足一个左区间，此时需乘上一个排列数：(egin{align}f[i+1][j+1-l_{i+1}][k+r_{i+1}]+=f[i][j][k] imes P_{ j+1}^{ l_{i+1}}end{align})
- 满足一个右区间，注意需要乘上左右两侧的方案数：(egin{align}f[i+1][j-l_{i+1}][k+r_{i+1}-1]+=f[i][j][k] imes P_{ j}^{ l_{i+1}} imes (k+r_{i+1})end{align})
- 都不满足，放在一个中间区间里，乘上左侧和中间的方案数：(egin{align}f[i+1][j-l_{i+1}][k+r_{i+1}]+=f[i][j][k] imes P_{ j}^{ l_{i+1}} imes mid_{i+1}end{align})
-
边界(f[0][0][0]=1)，答案(sum_{i=1}^{m}f[m][i][0])
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 60
#define M 210
#define R register
#define gc getchar
#define mod 1000000007
using namespace std;
typedef long long ll;
ll fac[M]={1},c[M][M]={1},ans;
ll n,m,l[M],r[M],mid[M],f[M][M][N];
inline ll rd(){
ll x=0; char c=gc();
while(!isdigit(c)) c=gc();
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return x;
}
int main(){
n=rd(); m=rd();
for(R ll i=1,llim,rlim;i<=n;++i){
++l[llim=rd()];
++r[m+1-(rlim=rd())];
for(R ll j=llim+1;j<=m-rlim;++j) ++mid[j];
}
for(R ll i=1;i<=m;++i){
c[i][0]=c[i][i]=1; fac[i]=(fac[i-1]*i)%mod;
for(R ll j=1;j<i;++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
f[0][0][0]=1;
for(R ll i=0;i<m;++i)
for(R ll j=0;j<=i;++j)
for(R ll k=0;k<=n;++k)
if(f[i][j][k]){
if(j+1>=l[i+1]) (f[i+1][j+1-l[i+1]][k+r[i+1]]+=f[i][j][k]*(c[j+1][l[i+1]]*fac[l[i+1]])%mod)%=mod;
if(j>=l[i+1]) (f[i+1][j-l[i+1]][k+r[i+1]]+=f[i][j][k]*(c[j][l[i+1]]*fac[l[i+1]]*mid[i+1])%mod)%=mod;
if(j>=l[i+1]&&k+r[i+1]) (f[i+1][j-l[i+1]][k+r[i+1]-1]+=f[i][j][k]*(c[j][l[i+1]]*fac[l[i+1]]%mod*(k+r[i+1])%mod)%mod)%=mod;
}
for(R ll i=0;i<=m;++i) (ans+=f[m][i][0])%=mod;
printf("%lld
",ans);
return 0;
}