「BZOJ2734」[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}。
「样例解释」
有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。
题解
写出如下矩阵
1 3 9 27…
2 6 18 54…
4 12 36 108…
发现最多有11列。。。
我们在其中选取一些数，相邻的不能选择
然后就可以状压求方案数了，但是5没有出现，同样5的倍数也没有出现，7也如此。。
应该记录哪些数字出现过，没出现过就作为矩阵的第一个元素，最后把若干个矩阵的方案相乘
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define mod 1000000001 #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll tot=1; int bin[20]; int n; int a[20][20],b[20],f[20][2048]; bool mark[100005]; int cal(int x) { memset(b,0,sizeof(b)); a[1][1]=x; for(int i=2;i<=18;i++) if(a[i-1][1]*2<=n) a[i][1]=a[i-1][1]*2; else a[i][1]=n+1; for(int i=1;i<=18;i++) for(int j=2;j<=11;j++) if(a[i][j-1]*3<=n) a[i][j]=a[i][j-1]*3; else a[i][j]=n+1; for(int i=1;i<=18;i++) for(int j=1;j<=11;j++) if(a[i][j]<=n) { b[i]+=bin[j-1]; mark[a[i][j]]=1; } for(int i=0;i<=18;i++) for(int x=0;x<=b[i];x++) f[i][x]=0; f[0][0]=1; for(int i=0;i<18;i++) for(int x=0;x<=b[i];x++) { if(f[i][x]) for(int y=0;y<=b[i+1];y++) if(((x&y)==0)&&((y&(y>>1))==0)) f[i+1][y]=(f[i][x]+f[i+1][y])%mod; } return f[18][0]; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<=n;i++) if(!mark[i])tot=(tot*cal(i))%mod; printf("%d",tot); return 0; } |
计数器 9320595
OI 课件=>
OI 课件=>
飘逸的思路……
您如何分析此题的复杂度？
不会啊。。。
黄学长又装弱了，因为这是按照整除关系构建的三角形图，所以三角形并不高，最坏的情况是第一行是1，最后第k行是2^k，深度是O(logn)的，每一行的元素最多也是O(logn)的，一个元素推到下一行的状态是O(2^k)的，越深枚举次数越多，但点数也越少，可以考虑对每个三角形图进行分析，一个很难达到的上界时间复杂度是O(nlogn)。
Orz
tql