远古大坑
神仙DP状态设计题
https://blog.csdn.net/white_elephant/article/details/83592103
从行的角度入手，无论如何都要状压
每列最多放一个，所以从列的角度入手
每列会左端点结束，右端点出现，以及空位
个数设为：l[i],r[i],md[i]
直接决定当前列填在哪一行很困难，若直接记录还有多少行左半边没有填，那么并不知道哪些行的左半边之后会消失，无法转移
所以在这个左半边消失的时刻进行安排位置！
只要考虑之前预留了多少列即可，这些列都是可以用的
右半边？
预留就不行了，因为“起点”不一样，不一定都能用
但是终点一样，这次没有填的右部分，下一列还是可以填，所以直接转移
状态：f[i][j][k]“填完前i列，还有j列是空的，右半部分还有k行左端点出现在i及之前，且没有放置”的方案数
转移枚举填什么即可
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=52; const int M=202; const int mod=1e9+7; int A[M][M]; int jie[M]; int n,m,f[M][M][N]; int l[M],r[M],md[M]; int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y; } void inc(int &x,int y){ x=ad(x,y); } int mul(int x,int y){ return (ll)x*y%mod; } int main(){ rd(n);rd(m); if(2*n>m){ puts("0");return 0; } jie[0]=1; for(reg i=1;i<=m;++i) jie[i]=(ll)jie[i-1]*i%mod; A[0][0]=1; for(reg i=1;i<=m;++i){ A[i][0]=1; for(reg j=1;j<=i;++j){ A[i][j]=ad(A[i-1][j],A[i-1][j-1]); } } for(reg i=1;i<=m;++i){ for(reg j=1;j<=i;++j){ A[i][j]=(ll)A[i][j]*jie[j]%mod; } } for(reg i=1;i<=n;++i){ int L,R;rd(L);rd(R); R=m-R+1; ++l[L];++r[R]; for(reg j=L+1;j<R;++j){ ++md[j]; } } f[0][0][0]=1; for(reg i=0;i<m;++i){ for(reg j=0;j<=i;++j){ for(reg k=0;k<=n;++k){ int lp=f[i][j][k]; if(lp){ if(j+1-l[i+1]>=0) inc(f[i+1][j+1-l[i+1]][k+r[i+1]],mul(lp,A[j+1][l[i+1]])); if(j-l[i+1]>=0&&k+r[i+1]>0) inc(f[i+1][j-l[i+1]][k+r[i+1]-1],mul(lp,mul(A[j][l[i+1]],k+r[i+1]))); if(j-l[i+1]>=0) inc(f[i+1][j-l[i+1]][k+r[i+1]],mul(lp,mul(A[j][l[i+1]],md[i+1]))); } } } } ll ans=0; for(reg j=0;j<=m;++j) ans=ad(ans,f[m][j][0]); ot(ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
考虑从列入手简单
但是直接记录剩下多少个没填很难，因为结束位置不同
所以考虑在最后结束位置进行分配，只要记录之前剩下多少
一种变相的对未来承诺，或者说是预留