F. Special Matrices (滾動dp)

F. Special Matrices (滾動dp)

題意

給定 n × n n\times n n×n的 01 01 01矩陣的前 m m m行，滿足 n × n n\times n n×n每行每列之和都為 2 2 2的方案數有多少個，

思路

令 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示對于當前第 i i i行有 j j j列可以填一個1，有 k k k列可以填2個1，

則目標狀態為： d p [ n + 1 ] [ 0 ] [ 0 ] dp[n+1][0][0] dp[n+1][0][0]，

分三種情況：

1.選兩個可以填 1 1 1的列
d p [ i ] [ j ] [ k ] + = d p [ i ? 1 ] [ j ? 2 ] [ k ] × j ( j ? 1 ) 2 dp[i][j][k]+=dp[i-1][j-2][k]\times \dfrac{j(j-1)}{2} dp[i][j][k]+=dp[i?1][j?2][k]×2j(j?1)?

2.選一個可以填1的，一個可以填2的列，

d p [ i ] [ j ] [ k ] + = d p [ i ? 1 ] [ j ] [ k ] × j × k dp[i][j][k]+=dp[i-1][j][k]\times j\times k dp[i][j][k]+=dp[i?1][j][k]×j×k

3.選兩個可以填2的，
d p [ i ] [ j ] [ k ] + = d p [ i ? 1 ] [ j + 2 ] [ k ? 2 ] × k ( k ? 1 ) 2 dp[i][j][k]+=dp[i-1][j+2][k-2]\times \dfrac{k(k-1)}{2} dp[i][j][k]+=dp[i?1][j+2][k?2]×2k(k?1)?

代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505,M=2e4+5,inf=0x3f3f3f3f;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
 int n,m,mod;
int dp[2][N][N];
int a[N];
ll C(ll n){
    return n*(n-1)>>1;
}
int main(){
    scanf("%d%d%d",&n,&m,&mod);
    int c1=0,c2=0;
    for(int j=1;j<=n;j++) a[j]=2;
    int x; 
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++)
            scanf("%1d",&x),a[j]-=x;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==1) c1++;
        else if(a[i]==2) c2++;
    }
   	x=0;
    dp[0][c1][c2]=1;
    for(int i=m+1;i<=n;i++){
    	x^=1;
        for(int j=0;j<=n;j++){	//這里j[0,n] 因為j可能增大. 
            int k=(((n-i+1)<<1)-j)>>1;
            if(k<0||k>c2) continue;//因為k只會越來越小[0,c2]是合法的. 
            if(j>=2) dp[x][j-2][k]=(dp[x][j-2][k]+1LL*dp[x^1][j][k]*C(j)%mod)%mod;
            if(k>=2) dp[x][j+2][k-2]=(dp[x][j+2][k-2]+1LL*dp[x^1][j][k]*C(k)%mod)%mod;
            if(j>=1&&k>=1) dp[x][j][k-1]=(dp[x][j][k-1]+1LL*dp[x^1][j][k]*j*k%mod)%mod;
        }
    }printf("%d\n",dp[x][0][0]);
	return 0;
}