第一行包含两个整数,N,M,其中1<=N<=50,2<=M<=200. 之后有N行,每行两个数left[i],right[i],其中,1<=left[i],right[i]<=M,且left[i]+right[i]<=M。Output
一个整数,即符合条件的方案数mod1,000,000,007后的结果。Input示例
24 12 21Output示例
1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
神奇DP+思路~
用fi][j][k]表示当前i列,有j列没有放棋子,k行的right不满足。那么我们为了满足left,就要在更新的时候记录已经有多少left,强制更新。
为了节省时间可以把a排序。
数组开小了WAWAWA……2333
#include#include #include #include using namespace std; #define mod 1000000007 #define ll long long int n,m,f[202][202][52],c[202][202],mi[202],ans,l,r,block; struct node{ int l,r; }a[51]; bool operator < (node u,node v) { return u.l==v.l ? u.r<> '9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void add(int &a,int b) { a+=b; if(a>=mod) a-=mod; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=m-read()+1; sort(a+1,a+n+1); for(int i=0;i<=201;i++) c[i][0]=1; for(int i=1;i<=201;i++) for(int j=1;j<=i;j++) add(c[i][j],c[i-1][j]+c[i-1][j-1]); mi[0]=1; for(int i=1;i<=201;i++) mi[i]=(ll)mi[i-1]*i%mod; for(int i=1;i<=201;i++) for(int j=1;j<=i;j++) c[i][j]=(ll)c[i][j]*mi[j]%mod; f[0][0][0]=1; for(int i=0;i i+1); for(int j=l-1;j<=i+1;j++) for(int k=0;k<=n-r;k++) { if(j+1>=l && l>=1) add(f[i+1][j+1-l][k+r],(ll)l*c[j][l-1]%mod*f[i][j][k]%mod); if(j>=l) { add(f[i+1][j+1-l][k+r],(ll)c[j][l]*f[i][j][k]%mod); if(k+r>=1) add(f[i+1][j-l][k+r-1],(ll)c[j][l]*f[i][j][k]%mod*(k+r)%mod); if(block) add(f[i+1][j-l][k+r],(ll)c[j][l]*f[i][j][k]%mod*block%mod); } } } for(int i=0;i<=m;i++) add(ans,f[m][i][0]); printf("%d\n",ans); return 0; }