2734: [HNOI2012]集合选数
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 560 Solved: 321[Submit][Status]
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}。
神奇的排列组合问题，其中分成多个独立子问题，分别转化为矩阵，最有用乘法原理合并的思想可以用在很多题里面。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100010
#define MOD 1000000001
typedef long long qword;
int gcd(
int x,
int y)
{
return (x%y==
0)?y:gcd(y,x%
y);
}
int pow(
int x,
int y)
{
int ret=
1;
while (y)
{
if (y&
1)ret*=
x;
x*=
x;
y>>=
1;
}
return ret;
}
qword pow_mod(qword x,int y)
{
qword ret=
1;
while(y)
{
if (y&
1)ret=ret*x%
MOD;
x=x*x%
MOD;
y>>=
1;
}
return ret;
}
int dp[
30][
1<<
12];
int ff[MAXN];
int main()
{
//freopen("input.txt","r",stdin);
int n,x,y;
scanf("%d",&
n);
int i,j,k,ii;
qword ans=
1;
memset(ff,-
1,
sizeof(ff));
for (i=
0;i<
12;i++
)
{
if ((
1<<i)<
MAXN)
ff[(1<<i)]=
i;
}
for (i=
0;i<MAXN;i++
)
if (ff[i]==-
1)ff[i]=ff[i-
1];
for (ii=
1;ii<=n;ii++
)
{
if (ii%
2==
0 || ii%
3==
0)
continue;
int l,r,mid;
l=
0,r=
12;
while (l+
1<
r)
{
mid=(l+r)>>
1;
if ((qword)ii*pow(
3,mid)<=
n)
l=
mid;
else
r=
mid;
}
memset(dp,0,
sizeof(dp));
dp[0][
0]=
1;
x=
ii;
for (i=
1;ii*(
1<<i>>
1)<=n;i++)
//log(n)
{
for (j=
0;j<(
1<<r);j++)
//2^(log3(n))
{
if (!dp[i-
1][j])
continue;
for (k=
0;k<(
1<<r);k++
)
{
if (j&k || (k&(k<<
1)))
continue;
if ((qword)x*pow(
3,ff[k])>n)
break;
dp[i][k]=(dp[i][k]+dp[i-
1][j])%
MOD;
}
}
x*=
2;
}
qword res=
0;
for (j=
0;j<(
1<<r);j++
)
{
res=(res+dp[i-
1][j])%
MOD;
}
ans=ans*res%
MOD;
}
printf("%lld\n",ans);
}
转载于:https://www.cnblogs.com/mhy12345/p/4109898.html
