一道非常妙的构造题 (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) 的倍数的数都类似的构造矩形，可以发现矩形内部元素不重复，然后根据乘法原理，将答案相乘即可。
#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
", Ans );
return 0;
}