[bzoj2734][DP]集合选数

2023-10-16 03:18

文章标签 dp 集合 bzoj2734 选数

本文主要是介绍[bzoj2734][DP]集合选数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

HINT

【样例解释】

有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。

题解

胡乱画一下你就可以发现
比如对于1来说，我们可以画出一个矩阵
1 3 9 27
2 6 18 54
4 12 36 108
…
右边是三倍下面是两倍，显然这个矩阵中四连通的不能一起选
又发现这个矩阵的行列都非常小，不会超过17和11
那就可以愉快地压列dp啦…
复杂度非常不满的…

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{int f=1,x=0;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;
}
int stack[20];
inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=2;
const int MAXM=(1<<12)+5;
const LL mod=1000000001;
int n,bin[25],is[MAXM],f[MAXN][MAXM],cnt[25];
void init()
{bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;for(int i=0;i<bin[12];i++)if(!(i&(i<<1))&&!(i&(i>>1)))is[i]=1;
}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int dp(int x)
{int li=0;while(x<=n){cnt[++li]=0;int temp=x;while(temp<=n)cnt[li]++,temp*=3;x*=2;}memset(f,0,sizeof(f));f[0][0]=1;int st=0;for(int i=1;i<=li;i++){st^=1;for(int j=0;j<bin[cnt[i]];j++)if(is[j]){int sum=0;for(int k=0;k<bin[cnt[i-1]];k++)if(is[k]&&!(j&k))ad(sum,f[st^1][k]);f[st][j]=sum;}}int re=0;for(int i=0;i<bin[cnt[li]];i++)if(is[i])ad(re,f[st][i]);return re;
}
int main()
{init();n=read();LL ans=1;for(int i=1;i<=n;i++)if((i%2)&&(i%3))ans=ans*(LL)dp(i)%mod;pr2(ans);return 0;
}