LG 3226 [HNOI2012]集合选数

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转为$x$构造一个矩阵满足$a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)$对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数这个矩阵长$\log_2 n$(不超过$17$),宽$\log_3 n$(不超过$12$),因此可以用状压 dp 解决我们只需要对不是$2,3$倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可……