$HNOI2012\ $ 集合选数 状压$dp$

时间：2021-08-24 06:33:57

\(Des\)

求对于正整数\(n\leq 1e5\),{\(1,2,3,...,n\)}的满足约束条件:"若\(x\)在该子集中,则\(2x\)和\(3x\)不在该子集中."的子集个数.

\(Sol\)

是一道很妙的构造+状压\(dp\)题吖.

我最开始想这题的时候画了一个如下的图.对于每一个点,左儿子是它的两倍,右儿子是它的三倍.

$HNOI2012\ $ 集合选数 状压$dp$

约束条件是:连了边的两个点是不可以同时选的,也就是只能隔一个选一个,但是这样显然不好做.于是考虑能不能再转化一下.仔细观察这个图会发现它特别像一棵树,但又不是,因为一个点有两个父亲,这是因为一个数可能是一个数的两倍同时又是另外一个数的三倍.再观察一下会发现这个图似乎是由许多小菱形组成的,于是把菱形拉成正方形会发现得到了一个倒三角.如下:

$HNOI2012\ $ 集合选数 状压$dp$

显然我们可以把这个倒三角填满得到一个网格图.对于每一个点,它的下面是它的两倍,右边是它的三倍.这样一来,约束条件就变成了选了一个数,就不能选与它相邻的数(上,下,左,右).转化之后就成为了一般的状压$dp $解决的问题.但是,注意到这个表格并不能涵盖所有的数,我们需要对没有被涵盖的数再建一个如上的网格图,最后乘法原理统计下答案就好了.

温馨提醒​

大数组别用\(memset\),你很有可能会向我一样\(T\)掉.

\(Code\)

Code

```cpp
#include
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
Ri x=0,y=1;char c=getchar();
while(c'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&cb[30];
bool vis[N];
il void build(Ri x)
{
mem(h,0);
while(xmod)f[i][j]-=mod;
}
}
ll ret=0;
go(j,0,(int)b[h[0]].size()-1)
{
ret=ret+f[h[0]][j];
if(ret>mod)ret-=mod;
}
return ret;
}
int main()
{
n=read();
go(i,1,n)
{
if(vis[i])continue;
build(i);as=as*sol();if(as>mod)as%=mod;
}
printf("%lld\n",as);
return 0;
}

<details>

随机推荐

  1. PLSQL&lowbar;闪回操作4&lowbar;Flashback Drop

    2014-06-25 Created By BaoXinjian

  2. 【转】堆栈跟踪中收到一个UnhandledExceptionFilter调用时，如何查找问题异常堆栈

    定义没有异常处理程序来处理引发的异常时调用UnhandledExceptionFilter函数.函数通常将异常传递到捕获并处理它所尝试的 Ntdll.dll 文件. 在某些情况下,在其中存在的进程内存 ...

  3. Java利用Rxtx进行串口通讯

    最近在做传感器数据采集的工作,底层是基于Zigbee的无线传感网络,所有数据采集到Zigbee协调器上然后通知上位机数据采集完成,上位机通过USB转串口去读取数据就可以了.那么问题来了,如何进行串口通 ...

  4. 安卓弹出对话框——Alertdialog（一）

    首先看各种样式的对话框: 我们看到,Dialog有很多的子类实现,所以我们要定义一个对话框,使用其子类来实例化一个即可,而不要直接使用Dialog这个父类来构造. 二.AlertDialog 今天我们 ...

  5. Oracle 数据库中在使用中文模糊查询时输入中文查询不到结果的解决方法

    添加环境变量 变量名:NLS_LANG 变量值:SIMPLIFIED CHINESE_CHINA.ZHS16GBK

  6. Turtle库的学习积累

    1.什么是turtle库 Python的Turtle库是一个直观有趣的图形绘制函数库,Turtle英文翻译过来是乌龟的意思,在绘图时可以想象成一只乌龟在移动. 2.绘图坐标体系 海龟的移动方向 3.绘 ...

  7. Cordova编译报AAPT错误的解决方法

    因为项目中同时使用cordova-hot-code-push-plugin和phonegap-plugin-barcodescanner,编译时报错:AAPT: error: resource and ...

  8. 函数模版和主函数分别在&period;h &period;cpp中&lpar;要包含&period;cpp&rpar;

    Complex.h #pragma once #include<iostream> using namespace std;//这句还必须加,要不然致错,不懂为啥呢 template &l ...

  9. 51Nod：1003 阶乘后面0的数量

    1003 阶乘后面0的数量  基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题  收藏  关注 n的阶乘后面有多少个0? 6的阶乘 = 1*2*3*4*5*6 = 72 ...

  10. 当点击onBackpress方法或者onKeyDown方法时出现不能响应的问题解决办法

    一般来讲,当我们点击手机上的back键之后,会直接调用activity的onbackpress()方法,或者我们也可以通过这样来进行捕捉点击事件 @Override public boolean on ...

相关文章