题目大意：给定n，求集合S={1,2,3,...,n}有多少子集满足对于任意集合中任意两个数x和y,x≠2y并且x≠3y

原题解见 http://www.cnblogs.com/Randolph87/p/3677786.html

对于n以内任意与6互质的整数x，我们列出一个矩阵

x 3x 9x 27x ...

2x 6x 18x 54x ...

4x 12x 36x 108x ...

...

向下是*2，向右是*3，这样这个矩阵的任意两个相邻的数都不能出现在同一集合中

方案数状压DP即可 最后把所有x的矩阵方案数用乘法原理乘在一起即可

很巧妙的一道题

#include
  
   
#include
   
     #include
    
      #include
     
       #define Mo 1000000001 using namespace std; int n,f[2][1<<12]; bool usable[1<<12]; long long ans=1; int State_Compression_DP(int now) { int i,j,s1,s2,last=0,re=0; memset(f,0,sizeof f); f[1][0]=1; for(i=0;now*(1<
      
       >1 ); for(j=0,temp=1;now*(1<
       
        >n; for(i=0;i<1<<12;i++) if( !(i>>1&i) && !(i<<1&i) ) usable[i]=1; for(i=1;i<=n;i++) if(i%2&&i%3) ans*=State_Compression_DP(i),ans%=Mo; printf("%d\n",(int)ans); return 0; }