Special Matrices(DP的优化)

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

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

难道就没法 $dp$ 了吗 $?$

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

设目前有 $x$ 列需要填充一个 $1$ ,有 $y$ 列需要填充两个 $1$

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

$f[i][j][q]$ 是截至到第 $i+m$ 行填充后,还剩下 $j$ 列需要放一个 $1$ , $q$ 列需要放两个 $1$

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

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

$f[i][j][q]+=f[i-1][j+2][q]*(j+2)*(j+1)/2$

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

$f[i][j][q]+=f[i-1][j+2][q]*(q+2)*(q+1)/2$

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

$f[i][j][q]+=f[i-1][j][q+1]*j*(q+1)$

滚动数组来优化空间,然后时间复杂度仍然是 $O(n^3)$

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

而填充 $i$ 行完之后,只有 $m-i$ 行需要填充

换句话说,枚举的 $j,q$ 条件 $j+q*2==(n-m-i)*2$

所以复杂度优化到 $O(n^2)$

#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];    
}