完全沒有思路，狀壓到死沒調出來……吐槽一下這題目描述的好不清楚啊好多人都理解錯題了……

題解：

真的挺神仙的，因為有每列最多放1個的限制，所以考慮按列dp，設f[i][j]表示考慮前i列在[1,i]中的右區間中有j個1，初始狀態f[0][0]=1;注：以下右區間表示[r[u],m];

記錄l，r的前綴和sl，sr，但是這兩個數組的含義并不一樣，sl[i]表示前i列中有多少行左區間已經結束，sr[i]表示的則是前i列中有多少行右區間已經開始。

轉移：首先只考慮第i列，枚舉右區間1的個數j，如果第i列不放1，那么$f[i][j]+=f[i-1][j]$,如果第i列放1，現在不考慮前i-1列的應響，$f[i][j]+=f[i-1][j-1]*(sr[i]-j+1)$,這里解釋一下這個$sr[i]-j+1$，在前i列包括sr[i]行的右區間可以放1，而前i-1列已經放了$j-1$個1占據了$（j-1）$行，所以第i列能放1的行數為$（sr[i]-(j-1)）$,由乘法計數原理得以上式子。但是我們這是沒有考慮前i列左區間的情況：同樣枚舉右區間放k個1，此時有（sl[i]-sl[i-1]）個左區間在第i列結尾，所以此時有（sl[i]-sl[i-1]）個1必須要放，而有i-k-sl[i-1]個位置可以放1，所以要乘$A_{i-k-sl[i-1]}^{sl[i]-sl[i-1]}$,如果不合法會變成負數。最后f[m][n]即為最后答案。

1 #include<iostream> 2 #include<cstdio> 3 #define LL long long 4 #define int LL 5 #define mod 998244353 6 #define MAXN 3010 7 using namespace std; 8 int n,m,l[MAXN],r[MAXN]; 9 int sl[MAXN],sr[MAXN],f[MAXN][MAXN]; 10 signed main() 11 { 12 cin>>n>>m; 13 for(int i=1;i<=n;i++)cin>>l[i]>>r[i],sl[l[i]]++,sr[r[i]]++; 14 for(int i=1;i<=m;i++)sl[i]+=sl[i-1],sr[i]+=sr[i-1]; 15 f[0][0]=1; 16 for(int i=1;i<=m;i++) 17 { 18 f[i][0]=f[i-1][0]; 19 for(int j=1;j<=i;j++) 20 f[i][j]=(f[i-1][j]+f[i-1][j-1]*(sr[i]-j+1)%mod)%mod; 21 for(int k=0;k<=i;k++) 22 for(int j=sl[i-1];j<sl[i];j++) 23 f[i][k]=f[i][k]*(i-k-j)%mod; 24 } 25 printf("%lld\n",f[m][n]); 26 } View Code

?

轉載于:https://www.cnblogs.com/Al-Ca/p/11286366.html

總結

以上是生活随笔為你收集整理的HZOJ matrix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。