Special Matrices(DP的优化)

水过(写这么详细是不是50nb呀!!!)

状态似乎无法压缩,假如压缩需要是一个长位的三进制数,不可取

难道就没法了吗

考虑到问题的特殊性,在确定了前行后,每列只需要放一个或者两个

设目前有列需要填充一个,有列需要填充两个

那么有行可以去填充数字,我们来枚举这行转移

是截至到第行填充后,还剩下列需要放一个,列需要放两个

那么枚举和,对当前行做出决策来转移

若本行选择的列都是需要放一个的,那么需要从列选出两列来

若本行选择的列都是需要放一个的,同理

若本行选择的两列,一个在需要放一个的列上,一个在需要放两个的列上

滚动数组来优化空间,然后时间复杂度仍然是

观察到由于每行只需要填充两个

而填充行完之后,只有行需要填充

换句话说,枚举的条件

所以复杂度优化到

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mod,col[504],f[2][504][504],ok[504];
char a[504][504],t,v;
void add(int &u,int v){ u = (u%mod+v%mod)%mod; }
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&mod);
    for(int i=1;i<=m;i++)    scanf("%s",a[i]+1);
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
        if( a[i][j]=='1' )    col[j]++;
    for(int i=1;i<=n;i++)    ok[2-col[i]]++;
    f[0][ok[1]][ok[2]] = 1;
    for(int i=1;i<=n-m;i++)
    {
        t = (i&1), v = t^1; int lim = 2*(n-m-i), li = min( ok[2],n-m-i );
        memset( f[t],0,sizeof f[t]);
        for(int q=0;q<=li;q++)//还剩下q个2 
        {
            int j = lim-q*2; if( j>n )    continue;
            f[t][j][q] = 0;
            int qq = (q+2)*(q+1)/2, jj = (j+2)*(j+1)/2;
            add( f[t][j][q], f[v][j][q+1]*j*(q+1) );    //选一个需要填一个的,一个需要填两个的 
            add( f[t][j][q], f[v][j+2][q]*jj );
            if( j>=2 )    add( f[t][j][q], f[v][j-2][q+2]*qq );
        }    
    }
    cout << f[t][0][0];    
}