[HNOI 2012]集合选数

时间:2022-09-01 18:15:10

Description

题库链接

对于任意一个正整数 \(n\) ,求出集合 \(\{1,2,\cdots,n\}\) 的满足约束条件“若 \(x\) 在该子集中,则 \(2x\) 和 \(3x\) 不能在该子集中”的子集的个数。

\(n\leq 100000\)

Solution

容易发现对于每一个与 \(2,3\) 互质的数 \(k\) ,我们构造一个 \(p\times q\) 的矩阵,该矩阵的第 \(i\) 行第 \(j\) 列表示数值 \(k\cdot 2^i3^j\) 。由于数值要 \(\leq n\) ,所以这个矩阵不是完整的。

显然对于这个矩阵,我选取的数不能相邻,由于 \(p,q\) 很小,可以用状压 \(DP\) 实现,来计算总方案数。

同样对于每个这样的 \(k\) 。可以随意组合所以将方案数乘起来就好了。

Code

//It is made by Awson on 2018.3.9
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int yzh = 1000000001, N = 200000;
void read(int &x) {
char ch; bool flag = 0;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); } int n, ans = 1, bin[20], f[20][N+5]; void work() {
read(n); bin[0] = 1; for (int i = 1; i <= 19; i++) bin[i] = bin[i-1]<<1;
for (int id = 1; id <= n; id++)
if (id%2 && id%3) {
int last = 0, now, tmp = id, k; f[0][0] = 1;
for (k = 1; tmp <= n; k++) {
for (now = 0; now <= 19; now++) if (tmp*bin[now] > n) break;
for (int i = 0; i < bin[now]; i++)
if ((i&(i>>1)) == 0) {
f[k][i] = 0;
for (int j = 0; j < bin[last]; j++)
if ((i&j) == 0 && (j&(j>>1)) == 0)
f[k][i] = (f[k][i]+f[k-1][j])%yzh;
}
last = now, tmp *= 3;
}
int t = 0;
for (int i = 0; i < bin[last]; i++) if ((i&(i>>1)) == 0) t = (t+f[k-1][i])%yzh;
ans = 1ll*ans*t%yzh;
}
writeln(ans);
}
int main() {
work(); return 0;
}

[HNOI 2012]集合选数的更多相关文章

  1. 【BZOJ-2732】集合选数 状压DP (思路题)

    2734: [HNOI2012]集合选数 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1070  Solved: 623[Submit][Statu ...

  2. bzoj 2734&colon; &lbrack;HNOI2012&rsqb;集合选数 状压DP

    2734: [HNOI2012]集合选数 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 560  Solved: 321[Submit][Status ...

  3. 【BZOJ2734】【HNOI2012】集合选数(状态压缩,动态规划)

    [BZOJ2734][HNOI2012]集合选数(状态压缩,动态规划) 题面 Description <集合论与图论>这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所 ...

  4. BZOJ&lowbar;2734&lowbar;&lbrack;HNOI2012&rsqb;集合选数&lowbar;构造&plus;状压DP

    BZOJ_2734_[HNOI2012]集合选数_构造+状压DP 题意:<集合论与图论>这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集:若 x ...

  5. 2734&colon; &lbrack;HNOI2012&rsqb;集合选数

    2734: [HNOI2012]集合选数 链接 分析: 转化一下题意. 1 3 9 27... 2 6 18 54... 4 12 36 108... 8 24 72 216... ... 写成这样的 ...

  6. &lbrack;HNOI2012&rsqb;集合选数 --- 状压DP

    [HNOI2012]集合选数 题目描述 <集合论与图论>这门课程有一道作业题,要求同学们求出\({1,2,3,4,5}\)的所有满足以 下条件的子集:若 x 在该子集中,则 2x 和 3x ...

  7. 【BZOJ-2734】集合选数 状压DP (思路题)

    2734: [HNOI2012]集合选数 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 1070  Solved: 623[Submit][Statu ...

  8. bzoj2734【HNOI2012】集合选数

    2734: [HNOI2012]集合选数 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 831  Solved: 487 [Submit][Stat ...

  9. 状压DP之集合选数

    题目 [HNOI2012]集合选数 <集合论与图论>这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集:若 x 在该子集中,则 2x 和 3x 不 ...

随机推荐

  1. font-family 字体

    宋体 SimSun黑体 SimHei微软雅黑 Microsoft YaHei微软正黑体 Microsoft JhengHei新宋体 NSimSun新细明体 PMingLiU细明体 MingLiU标楷体 ...

  2. &lbrack;开发工具&rsqb;Java开发常用的在线工具

    注明: 本文转自http://www.hollischuang.com/archives/1459.作为一个Java开发人员,经常要和各种各样的工具打交道,除了我们常用的IDE工具以外,其实还有很多工 ...

  3. 记 FineUI 官方论坛所遭受的一次真实网络攻击!做一个像 ice 有道德的黑客!

    在开始正文之前,请帮忙为当前 排名前 10 唯一的 .Net 开源软件 FineUI  投一票: 投票地址: https://code.csdn.net/2013OSSurvey/gitop/code ...

  4. 扩展struts2的结果集StrutsResultSupport 自定义Result处理JSON

    以前在采用Struts2开发的项目中,对JSON的处理一直都在Action里处理的,在Action中直接Response,最近研读了一下Struts2的源码,发现了一个更加优雅的解决办法,自己定义一个 ...

  5. erlang和java通信

    连接在 https://guts.me/2014/07/27/erlang-communicates-with-java/ 代码在 https://github.com/mingshun/jinter ...

  6. Linux网络管理——Linux网络命令

    3. Linux网络命令 .note-content {font-family: "Helvetica Neue",Arial,"Hiragino Sans GB&quo ...

  7. DatabaseMetaData的用法&lpar;转&rpar;

    http://blog.csdn.net/sdliubo/article/details/6546889

  8. SQL笔试基础

    SQLSERVER服务器中,给定表table1 中有两个字段 ID.LastUpdateDate,ID表示更新的事务号,LastUpdateDate表示更新时的服务器时间,请使用一句SQL语句获得最后 ...

  9. BZOJ1042 HAOI2008硬币购物(任意模数NTT&plus;多项式求逆&plus;生成函数&sol;容斥原理&plus;动态规划)

    第一眼生成函数.四个等比数列形式的多项式相乘,可以化成四个分式.其中分母部分是固定的,可以多项式求逆预处理出来.而分子部分由于项数很少,询问时2^4算一下贡献就好了.这个思路比较直观.只是常数巨大,以 ...

  10. linux下有线网卡出现ADDRCONF&lpar;NETDEV&lowbar;UP&rpar;&colon; eth0&colon; link is not ready的解决方法

    一.背景 2018年5月24日,笔者的pc已经连续运转两天了,突然要使用有线网卡,却发现有线网卡无法正常工作,于是查看了一下内核日志: r8169 0000:05:00.0 eth0: link do ...