Find the number of n*m 01 matrices that meet the following conditions:
(1) There is exactly one 1 in the i-th row and columns 1 to li.
(2) There is exactly one 1 in the ri~m column of the i-th row.
(3) There is at most 1 1 in each column
This question is still very interesting. I will figure out the dp method by simulating a sample.
The most difficult thing to think of is to list it by column. Enumeration…
See code comments for details
Code:
#include#define ll long long#define mod 998244353#define N 3005#define pos1 (rsum[i]-j+1)#define pos2 (ijk)using namespace std;int n,m;ll f[N][N],delta1,delta2;//f[ i][j] means that 1 is placed in the right interval of column j in the first i column ll lsum[N],rsum[N]; // How many 1~l and r~m have been placed 1 struct Limit{ ll l ,r;}a[N];template inline void read(T &res){ char c;T flag=1; while((c=getchar())<'0'||c>'9' )if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+ c-'0';res*=flag;}ll Mod(ll x){return x%mod;}int main(){ freopen("matrix.in","r",stdin); freopen("matrix. out","w",stdout); read(n);read(m); for(register int i=1;i<=n;++i) {read(a[i].l); read( a[i].r); lsum[a[i].l]++; rsum[a[i].r]++;} f[0][0]=1; for(register int i=1 ;i<=m;++i)//i column before enumeration {f[i][0]=f[i-1][0]; lsum[i]=lsum[i]+lsum[i- 1]; rsum[i]=rsum[i]+rsum[i-1]; for(register int j=1;j<=i;++j) {delta1=Mod(f[i-1][j]);//Without 1 on the right, transfer directly delta2=Mod(f[i- 1][j-1]*pos1);//Put 1 on the right, multiply the number of solutions by the remaining position f[i][j]=Mod(delta1+delta2);} for(register int j=lsum[i- 1];j<=lsum[i]-1;++j)//How many are left of the enumeration 1 {for(register int k=0;k<=i;++k)//Total k 1 is placed in the right interval f[i][k]=Mod(f[i][k]*pos2);//contribution=number of projects*remaining position}} printf("%lld ",f[m] [n]); return 0;}/*5 20060 17050 12080 9070 11080 100*/