Special Matrices

做法：dp+滚动数组优化

思路：

• 1.先求出已知前m项后每列还需要的几个1
• 2.然后枚举m+1~n行根据上一层状态来转移
  如果上层不存在某种状态直接continue
  1)补两列1个1 --->(转移后) 两列0个1
  2)补一列1个1+一列2个1 ---> 一列0个1+一列1个1
  3)补两列2个1 ---> 两列1个1
• 3.因为只需要从知道上一层状态，所以可以滚动数组优化，防止爆内存

代码

// Problem: Special Matrices
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/110736
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=505;
const int INF=0x3f3f3f3f;
// const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

ll n,m,mod;
char c;
ll f[2][N][N];
int cnt[N];


void solve(){
    cin>>n>>m>>mod;
    rep(i,1,n) cnt[i]=2;
    rep(i,1,m) rep(j,1,n)  cin>>c,cnt[j]-=(c-'0');
    ll ans1=0,ans2=0;
    rep(i,1,n) ans1+=(cnt[i]==1),ans2+=(cnt[i]==2);

    f[m&1][ans1][ans2]=1;

    for(int i=m+1;i<=n;i++){
        rep(j,0,n) rep(k,0,n) f[i&1][j][k]=0;
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(f[(i-1)&1][j][k]==0) continue;
                if(j>=2) f[i&1][j-2][k]+=(f[(i-1)&1][j][k]*(j*(j-1)/2%mod))%mod,f[i&1][j-2][k]%=mod;
                if(j>=1&&k>=1) f[i&1][j][k-1]+=f[(i-1)&1][j][k]*j%mod*k%mod,f[i&1][j][k-1]%=mod;
                if(k>=2) f[i&1][j+2][k-2]+=(f[(i-1)&1][j][k]*(k*(k-1)/2%mod))%mod,f[i&1][j+2][k-2]%=mod;
            }
        }
    }

    cout<<f[n&1][0][0]<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}