\(\\\)

---

给出一张\(N\times M\)的棋盘，每个格子最多放置一个棋子，一个合法的放置方案需满足：

• 每列至多放置一个棋子
• 对于第\(i\)行，前\(L_i\)个格子中恰好只放一个，后\(R_i\)个格子中恰好只放一个

求合法方案数对\(10^9+7\)取模后的值。

• \(N\in [1,50]\)，\(M\in [2,200]\)，\(L_i,R_i\in [1,M]\)，\(L_i+R_i\le M\)

\(\\\)

\(Solution\)

---

打死都想不到状态设计

注意到行之间无法记录以上各列状态直接转移，所以以列为状态。

考虑只有左边的限制：

• 设计\(f[i][j]\)表示处理到前\(i\)列，还有\(j\)列未放置棋子的方案数。
• 考虑状态向后更新，每次做到第\(i\)列，统计左区间限制的右端点为下一列的行数\(l_{i+1}\)，则下一列的这些限制都必须完成，因为这些行在哪一列被满足顺序无关，所以需要乘上排列，有\(f[i+1][j+1-l_{i+1}]+=f[i][j]\times 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\)。

• 同样每次到达左区间限制的右边界时，再考虑如何满足这些左区间，本列的放置考虑三种：
  • 满足一个左区间，此时需乘上一个排列数：\(\begin{align}f[i+1][j+1-l_{i+1}][k+r_{i+1}]+=f[i][j][k]\times P_{\ j+1}^{\ l_{i+1}}\end{align}\)
  • 满足一个右区间，注意需要乘上左右两侧的方案数：\(\begin{align}f[i+1][j-l_{i+1}][k+r_{i+1}-1]+=f[i][j][k]\times P_{\ j}^{\ l_{i+1}}\times (k+r_{i+1})\end{align}\)
  • 都不满足，放在一个中间区间里，乘上左侧和中间的方案数：\(\begin{align}f[i+1][j-l_{i+1}][k+r_{i+1}]+=f[i][j][k]\times P_{\ j}^{\ l_{i+1}}\times mid_{i+1}\end{align}\)

• 边界\(f[0][0][0]=1\)，答案\(\sum_{i=1}^{m}f[m][i][0]\)

\(\\\)

\(Code\)

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 60#define M 210#define R register#define gc getchar#define mod 1000000007using 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
           
            =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\n",ans); return 0;}