程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj2734【HNOI2012】集合選數

bzoj2734【HNOI2012】集合選數

編輯:C++入門知識

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

HINT

Source

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>

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved