自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 21:46:42，当前版本为作者最后更新于2019-04-03 12:04:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道非常妙的构造题 $QwQ$

要 $2x$， $3x$ 都不在集合内，但直接处理貌似非常不好，所以我们需要构造出一个与原命题等价的命题。

貌似是这个，构造一个矩形，第一行第一列的元素为$1$，第一行的后面所有数均为前面的数的两倍。

接下来每列的数都是它上面的数的三倍。

大概构造出来长这样：

1  2  4  8   16  32  ...
3  6  12 24  48  96  ...
9  18 36 72  ...
27 ...

那么对于这个矩形内，我们要做的就是求出这个矩形内，选出一些数，相邻的数不能选的方案数。

因为每个数都是前面那个数的 $2$ 倍，所以这个矩形最后长为 $log_2n$，宽为$log_3n$大概是 $17,12$ 不到的样子。

可以用状压$dp$解决

但是这个矩形并没有涵盖所有的数，所以我们需要对每个即不是 $2$ 的倍数又不是 $3$ 的倍数的数都类似的构造矩形，可以发现矩形内部元素不重复，然后根据乘法原理，将答案相乘即可。

复杂度大概是$O($能过$)$

#include<bits/stdc++.h>
using namespace std;
int read() {
	char cc = getchar(); int cn = 0, flus = 1;
	while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
	while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
	return cn * flus;
}
#define int long long
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i ) 
const int mod = 1000000001;
const int maxn = ( 1 << 18 ) - 1;
const int N = 100000 + 5;
const int M = 20 ;
int n, book[N], Ans, line[M], g[maxn], a[M][M], end, dp[M][maxn], num, lim[M];
void init( int x ) {
	rep( i, 1, 11 ) {
		if( i == 1 ) a[i][1] = x;
		else a[i][1] = a[i - 1][1] * 3;
		//初始化矩形 
		if( a[i][1] > n ) break ;
		
		end = i, line[i] = 1, book[a[i][1]] = 1;
		//line表示第i行有多少列 
		rep( j, 2, 18 ) {
			a[i][j] = a[i][j - 1] * 2;
			if( a[i][j] > n ) break;
			line[i] = j, book[a[i][j]] = 1; // 用book标记这个元素被选过 
		}
		lim[i] = ( 1 << line[i] ) - 1; // lim表示第i行的数有多少个，起限制作用 
	}
}
void solve(int x) {
	num = 0 ;
	rep( i, 0, lim[1] ) dp[1][i] = g[i];
	rep( i, 2, end ) rep( j, 0, lim[i] ) {
		if( !g[j] ) continue ; //如果状态j不合法，就跳过 
		dp[i][j] = 0;
		rep( k, 0, lim[i - 1] )
			if( g[k] && ( (k & j) == 0 ) ) //如果状态k合法，且k与j没有位置相同 
			dp[i][j] += dp[i - 1][k], dp[i][j] %= mod;
	}
	rep( i, 0, lim[end] ) num += dp[end][i], num %= mod ;
}
signed main()
{
	n = read() ; Ans = 1;
	rep( i, 0, maxn ) g[i] = ( (i << 1) & (i) ) ? 0 : 1; //初始化哪些状态合法。 
	
	rep( i, 1, n ) if( !book[i] )  //如果这个数没有被选过。 
		init(i), solve(i), Ans = Ans * num % mod; //先构造矩形，然后状压dp 
	
	printf("%lld\n", Ans );
	return 0;
}