题目链接

题解

构造矩阵的思路真的没想到

选\(x\)就不能选\(2x\)和\(3x\)，会发现实际可以转化为矩阵相邻两项

\[\begin{matrix}1 & 3 & 9 & 27 & ... \\2 & 6 & 18 & 54 & ... \\4 & 12 & 36 & 108 & ... \\8 & 24 & 72 & 216 & ... \\ ... & ... &... &... &... \\ \end{matrix}
\]

相当于选这样的矩阵中不相邻的若干项的方案数

我们取每一个不是\(2\)和\(3\)的倍数的数作为矩阵左上角

行数和列数都很小，可以状压\(dp\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 20,maxm = (1 << 12),INF = 1000000000,P = 1000000001;

int f[maxn][maxm];

int N,n,cnt[maxn];

int ill[maxm],ans = 1;

void init(){

	int t = 3;

	for (int s = 0; s < maxm; s++){

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

			if (((s & (t << i)) >> i) == t){

				ill[s] = true; break;

			}

	}

}

void dp(int x){

	for (n = 0; x <= N; x *= 2){

		cnt[++n] = 0;

		int t = x;

		while (t <= N) cnt[n]++,t *= 3;

	}

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

		for (int s = 0; s < (1 << cnt[i]); s++)

			f[i][s] = 0;

	for (int s = 0; s < (1 << cnt[1]); s++)

		if (!ill[s]) f[1][s] = 1;

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

		for (int s = 0; s < (1 << cnt[i]); s++){

			if (ill[s]) continue;

			for (int e = 0; e < (1 << cnt[i - 1]); e++){

				if (ill[e]) continue;

				if (!(s & e)){

					f[i][s] = (f[i][s] + f[i - 1][e]) % P;

				}

			}

		}

	int re = 0;

	for (int s = 0; s < (1 << cnt[n]); s++)

		re = (re + f[n][s]) % P;

	ans = 1ll * ans * re % P;

}

int main(){

	init();

	scanf("%d",&N);

	for (int i = 1; i <= N; i++){

		if (i % 2 == 0 || i % 3 == 0) continue;

		dp(i);

	}

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

	return 0;

}

巴特西

BZOJ3724 [HNOI2012]集合选数【状压dp】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ3724 [HNOI2012]集合选数 【状压dp】

题目链接

题解

最新文章

热门文章

BZOJ3724 [HNOI2012]集合选数【状压dp】