首页 > 代码库 > BZOJ2734[HNOI2012]集合选数

BZOJ2734[HNOI2012]集合选数

2024-09-01 07:47:29   217人阅读

Description

《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目，于是把它变成了以下问题：对于任意一个正整数 n≤100000，如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就 交给你了。 

Input

 只有一行，其中有一个正整数 n，30%的数据满足 n≤20。 

Output

 仅包含一个正整数，表示{1, 2,..., n}有多少个满足上述约束条件 的子集。 

Sample Input

4

Sample Output

8
【样例解释】
有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
 
题解：
设x为一个不含2与3因子的数，则可以构造出一个这样的矩阵：
x x*3 x*3^2 x*3^3 . . .
2*x 2*x*3 2*x*3^2 2*x*3^3 . . .
2^2*x 2^2*x*3  2^2*x*3^2 2^2*x*3^3 . . .
2^3*x 2^3*x*3  2^3*x*3^2 2^3*x*3^3 . . .
. . . . . . .
. . . . . . .
. . . . . . .
 
 
 
 
 
 
 
 
 
 
例如x=1时：
 1   3   9  27 . . .
   2       6       18       54    . . .
   4       12       36       108    . . .
8 24 72 216 . . .
. . . . . . .
. . . . . . .
. . . . . . .
 
 
 
 
 
 
 
 
 
 
如此一来，不能同时取的数对在矩阵中一定是左右或是上下相邻的。因为n<=1000000，所以矩阵最多有11列，可以将每一行进行状态压缩DP。
每个数一定且只存在于一个矩阵之中，两个矩阵之间没有关联，所以DP出每个矩阵的可行方案数，最后相乘就可以了。
 
代码：
技术分享 
 1 const
 2   mo=1000000001;
 3 var
 4   i,j,k,l,n,m:longint;
 5   a:array[0..20,0..20]of longint;
 6   b:array[0..20]of longint;
 7   f:array[0..20,0..2048]of longint;
 8   bo:array[0..100005]of longint;
 9   bin:array[0..20]of longint;
10   ans:int64;
11 function qq(x:longint):longint;
12 var i,j,y:longint;
13 begin
14   fillchar(b,sizeof(b),0);
15   a[1,1]:=x;
16   for i:=2 to 18 do
17   if a[i-1,1]*2<=n then a[i,1]:=a[i-1,1]*2 else a[i,1]:=n+1;
18   for i:=1 to 18 do
19   for j:=2 to 11 do
20   if a[i,j-1]*3<=n then a[i,j]:=a[i,j-1]*3 else a[i,j]:=n+1;
21   for i:=1 to 18 do
22   for j:=1 to 11 do
23   if a[i,j]<=n then
24   begin
25     b[i]:=b[i]+bin[j-1];
26     bo[a[i,j]]:=1;
27   end;
28   for i:=0 to 18 do
29   for j:=0 to b[i] do f[i,j]:=0;
30   f[0,0]:=1;
31   for i:=0 to 17 do
32   for j:=0 to b[i] do
33   if f[i,j]>0 then
34   for y:=0 to b[i+1] do
35   if(j and y=0)and(y and(y shr 1)=0)then f[i+1,y]:=(f[i+1,y]+f[i,j])mod mo;
36   exit(f[18,0]);
37 end;
38 begin
39   bin[0]:=1;
40   for i:=1 to 20 do bin[i]:=bin[i-1]shl 1;
41   readln(n); ans:=1;
42   for i:=1 to n do
43   if bo[i]=0 then ans:=(ans*qq(i))mod mo;
44   writeln(ans);
45 end.
View Code
 

BZOJ2734[HNOI2012]集合选数


联系
我们