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

BZOJ 2734 HNOI2012 集合選數 狀壓DP

編輯:C++入門知識

BZOJ 2734 HNOI2012 集合選數 狀壓DP


題目大意:給定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;
}


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