《集合論與圖論》這門課程有一道作業題，要求同學們求出{1, 2, 3, 4, 5}的所有滿足以 下條件的子集：若 x 在該子集中，則 2x 和 3x 不能在該子集中。同學們不喜歡這種具有枚舉性 質的題目，於是把它變成了以下問題：對於任意一個正整數 n≤100000，如何求出{1, 2,..., n} 的滿足上述約束條件的子集的個數（只需輸出對 1,000,000,001 取模的結果），現在這個問題就 交給你了。
只有一行，其中有一個正整數 n，30%的數據滿足 n≤20。
僅包含一個正整數，表示{1, 2,..., n}有多少個滿足上述約束條件 的子集。
day2
狀壓DP思路好題
寫出這樣一個矩陣
1 3 9 27 …
2 6 18 54 …
4 12 36 108 …
…
可以發現最多有12行。
這樣我們只要枚舉左上角的數x，就可以得到一個不同的矩陣，對於每一個矩陣需要選一些數，但不能選相鄰的數，狀壓DP解決。
對於每一個矩陣，把方案數相乘即為答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
#define mod 1000000001
using namespace std;
int n;
ll ans=1,f[20][4100],num[20];
bool vst[maxn];
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;
}
inline ll calc(int x)
{
int cnt=0;
memset(num,0,sizeof(num));
memset(f,0,sizeof(f));
f[0][0]=1;
while (x<=n)
{
cnt++;
int tmp=x;
while (tmp<=n)
{
num[cnt]++;
vst[tmp]=true;
tmp*=3;
}
F(i,0,(1<<num[cnt])-1) if="" int="" ll="" n="read();" p="1;p<num[cnt];p++)" pre="" return="" t="0;"><p>
</p>
</num[cnt])-1)></algorithm></cstdlib></cmath></cstring></cstdio></iostream>
