BZOJ2734 (集合选数)[状压DP, 矩阵]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1087

考虑到选取集合中的元素不能是乘2或乘3相邻，我们尝试构造一个矩阵：
$$
\begin{bmatrix}
x & 3x & 9x & \cdots \\
2x & 6x & 18x & \cdots \\
4x & 12x & 36x & \cdots \\
\vdots & \vdots & \vdots & \ddots \\
\end{bmatrix}
$$
这样只需要在矩阵中选取不相邻的元素就能满足题意了。
这个矩阵的长宽是log级的，因此问题转化成了类似互不侵犯King的问题。
$x$代入不是2或3倍数的数构造多个矩阵，结果根据乘法原理相乘就是答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const ll M=1000000001;
int n;
int col[18];
ll dp[18][2049];
ll f(int x) {
	memset(col,0,sizeof(col));
	memset(dp,0,sizeof(dp));
	int r=0;
	for(int i=x;i<=n;i*=2) {
		r++;
		int c=1;
		for(int j=i*3;j<=n;j*=3) c++;
		col[r]=1<<c;
	}
	col[0]=1; 
	dp[0][0]=1;
	for(int i=1;i<=r;i++) {
		for(int j=0;j<col[i];j++) {
			if(!(j&(j<<1))) {
				for(int k=0;k<col[i-1];k++) 
					if(!(k&(k<<1)) && !(j&k)) 
						dp[i][j]=(dp[i][j]+dp[i-1][k])%M;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<col[r];i++) 
		ans=(ans+dp[r][i])%M;
	return ans;
}
int main() {
	scanf("%d",&n);
	ll ans=1;
	for(int i=1;i<=n;i++) 
		if(i%2 && i%3) 
			ans=(ans*f(i))%M;
	printf("%lld",ans);
}