一本通高手训练 1782 分层图状压dp

LINK：分层图

很精辟的一道题写的时候没带脑子导致搞了半天不知道哪错了。

可以想到状压每次到某一层的状态然后这个表示方案数多开一维表示此时路径条数的奇偶即可。

不过显然我们只需要知道路径条数的奇偶性即可。

所以对于当前状态如果某个点路径条数为偶数那么怎么转移都不必要所以我们可以不需要多开一维状态来进行转移。

状态直接表示成奇偶性即可。

考虑转移容易发现转移需要求出当前点集能到的下一层的点集然后还要求出奇偶性。

暴力枚举复杂度\(mk2^k\) 容易想到不需要暴力枚举然后使用lowbit操作这样降低一倍常数。

当然还可以使用dp 求出这些点集具体操作还是lowbit 考虑除下当前最小的那位的状态求出过了直接加上当前点的贡献即可。

总复杂度\(m2^k\)

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define S second

#define F first

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define ull unsigned long long

#define ui unsigned

#define zz p<<1

#define yy p<<1|1

#define EPS 1e-8

#define mod 998244353

#define sq sqrt

#define len(p) t[p].len

#define f(p) t[p].fa

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}

    return x*f;

}

const int MAXN=10010,N=10;

int n,m;

int f[MAXN][1<<N];//f[i][j]表示当前到达第i层到第j个点的方案数的状态.

int w[MAXN][N+1],g[MAXN][N+1],pos[1<<N],w1[1<<N],w2[1<<N];

int main()

{

	//freopen("1.in","r",stdin);

	get(n);get(m);

	rep(1,n-1,i)

	{

		if(i==1||i==n-1)

		{

			if(i==1)rep(1,m,j)w[i][1]|=(read()<<(j-1));

			if(i==n-1)rep(1,m,j)w[i][j]=read();

			continue;

		}

		rep(1,m,j)rep(1,m,k)

		{

			int x=read();

			w[i][j]|=(x<<(k-1));

			g[i][k]|=(x<<(j-1));

		}

	}

	f[1][1]=1;

	int maxx=(1<<m)-1;

	rep(1,m,i)pos[1<<(i-1)]=i;

	rep(1,n-1,i)

	{

		rep(0,maxx,j)

		{

			w1[j]=w1[j-(j&(-j))]^w[i][pos[j&(-j)]];

			w2[j]=w2[j-(j&(-j))]^g[i][pos[j&(-j)]];

			if(!f[i][j])continue;

			int s=w1[j],s2=w2[j];

			f[i+1][s]=(f[i+1][s]+f[i][j])%mod;

			if(i!=1&&i!=n-1)f[i+1][s2]=(f[i+1][s2]+f[i][j])%mod;

		}

	}

	put(f[n][0]);

	return 0;

}

巴特西

一本通高手训练 1782 分层图状压dp

最新文章

热门文章

巴特西

一本通 高手训练 1782 分层图 状压dp

最新文章

热门文章

一本通高手训练 1782 分层图状压dp