2734: [HNOI2012]集合选数

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}。

一开始是这样想的，不能一起选的连一条边然后在图上dp

2 3

4 6 9

8 12 18

但是好像不行

看了题解才知道

我们把图弄成这样（往下走是*2，往右走是*3，就变成相邻的数不能选，可以用状压dp）

1 3 9

2 6 18

4 12 36

8 24 72

............

但是要注意这个时候我们并没有把所有的数都考虑到，比如5的倍数，所以我们枚举左上角的数，然后用乘法定理

具体做法是用一个flag存这个数是否考虑过，没考虑就把他当做左上角的数做一遍

 const

         h=;

         maxn=;

 var

         f:array[..,..]of longint;

         num:array[..]of longint;

         flag:array[..maxn]of boolean;

         n:longint;

         ans:int64;

 function get(x:longint):int64;

 var

         i,j,k,s,w:longint;

 begin

         get:=;

         s:=x;

         w:=x;

         flag[x]:=true;

         num[]:=;

         while w*<=n do

           begin

             w:=w*;

             flag[w]:=true;

             inc(num[]);

           end;

         for j:= to <<(num[])- do

           if j and(j<<)= then f[,j]:=;

         i:=;

         while s*<=n do

           begin

             inc(i);

             s:=s*;

             w:=s;

             num[i]:=;

             flag[w]:=true;

             while w*<=n do

               begin

                 w:=w*;

                 flag[w]:=true;

                 inc(num[i]);

               end;

             for j:= to <<(num[i])- do

               f[i,j]:=;

             for j:= to <<(num[i])- do

               for k:= to <<(num[i-])- do

                 if (j and(j<<)=) and (j and k=) then f[i,j]:=(f[i,j]+f[i-,k])mod h;

           end;

         for j:= to <<(num[i])- do

           inc(get,f[i,j]);

 end;

 procedure main;

 var

         i:longint;

 begin

         read(n);

         ans:=;

         for i:= to n do

           if flag[i]=false then ans:=(ans*get(i))mod h;

         writeln(ans);

 end;

 begin

         main;

 end.

巴特西

2734: [HNOI2012]集合选数 - BZOJ

最新文章

热门文章