一道状压dp水题

时间:2022-12-18 13:21:01

一道状压dp水题


枚举它的每一行,对它状压一下就好

然后转移的时候要O(k) 所以预处理一下每个数字里由多少1就行了(考试时用了bitset 思想江化了)


#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

#define inf 1000000007
#define mod 998244353
#define ll long long
#define N 2010

int m,k;
ll f[N*5][N],ans;
int num[N];
int main()
{
    register int i,j,o,x=0,tt;
    m=read();k=read();
    int tp[13],t2[13];
    for(i=1;i<=k;++i) x=x<<1|read();
    f[1][x]=1;
    for(i=1;i<(1<<k);++i)num[i]=num[i>>1]+(i&1);
    for(i=1;i<(1<<k);++i)num[i]=(num[i]&1)?1:0;
    for(i=2;i<m-1;++i)
    {
        memset(tp,0,sizeof(tp));
        memset(t2,0,sizeof(t2));
        for(j=1;j<=k;++j)for(o=1;o<=k;++o)
	{x=read();tp[o]=tp[o]<<1|x;t2[j]=t2[j]<<1|x;}
        for(j=0;j<(1<<k);++j)
        {
            tt=x=0;
            for(o=1;o<=k;++o)
            {x=x<<1|num[j&tp[o]];tt=tt<<1|num[j&t2[o]];}
            (f[i][x]+=f[i-1][j])%=mod;
            (f[i][tt]+=f[i-1][j])%=mod;
        }
    }
    for(i=1,x=0;i<=k;++i) x=x<<1|read();
    for(i=0;i<(1<<k);++i)
    {if(!num[i&x]){ans+=f[m-2][i];ans%=mod;}}
    printf("%lld\n",ans);
    return 0;
}