[BZOJ2734][HNOI2012] 集合选数（状态压缩+思维）

Description

题目链接

Solution

可以根据条件构造出一个矩阵，

1 3 9 27 81...

2 6 18....

4 12 36...

这个矩阵满足\(G[i][1]=G[i-1][1]*2(1< i),G[i][j]=G[i][j-1]*3(1\leq i,1<j)\)

也就是要满足不能同时选择矩阵中\((G[i][j],G[i][j+1],G[i+1][j])\)

而且会发现，矩阵可能有多个，应枚举矩阵的\(G[1][1]\)并记录下出现过的数

这样会发现矩阵最大长为18，最大宽为11，容易想到状压DP记录一下方案数即可

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 100010

using namespace std;

const int mo=1000000001;

int n,g[20][20],b[20],dp[20][2049],Ans=1;

bool vis[N];

int DP(int x){

	memset(b,0,sizeof(b));

	memset(g,0x3f,sizeof(g));

	memset(dp,0,sizeof(dp));

	g[1][1]=x;

	for(int i=2;i<=18&&g[i-1][1]*1ll*2<=n;++i) g[i][1]=g[i-1][1]*2;

	for(int i=1;i<=18;++i)

		for(int j=2;j<=11&&g[i][j-1]*1ll*3<=n;++j)

			g[i][j]=g[i][j-1]*3;

	for(int i=1;i<=18;++i)

		for(int j=1;j<=11;++j)

			if(g[i][j]<=n) b[i]|=(1<<(j-1)),vis[g[i][j]]=1;

	dp[0][0]=1;

	for(int i=0;i<18;++i)

		for(int S=0;S<=b[i];++S)

			if(dp[i][S])

				for(int nxS=0;nxS<=b[i+1];++nxS)

					if(((S&nxS)==0)&&((nxS&(nxS>>1))==0))//满足限制

						(dp[i+1][nxS]+=dp[i][S])%=mo;

	return dp[18][0];

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

		if(!vis[i]) Ans=(Ans*1ll*DP(i))%mo;//乘法原理

	printf("%d\n",Ans);

	return 0;

}

巴特西

[BZOJ2734][HNOI2012] 集合选数（状态压缩+思维）

Description

Solution

Code

最新文章

热门文章