bzoj 2734: [HNOI2012]集合选数状压DP

2023-08-15 20:59:58

2734: [HNOI2012]集合选数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 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

Sample Output

【样例解释】

有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==)?y:gcd(y,x%y);

}

int pow(int x,int y)

{

        int ret=;

        while (y)

        {

                if (y&)ret*=x;

                x*=x;

                y>>=;

        }

        return ret;

}

qword pow_mod(qword x,int y)

{

        qword ret=;

        while(y)

        {

                if (y&)ret=ret*x%MOD;

                x=x*x%MOD;

                y>>=;

        }

        return ret;

}

int dp[][<<];

int ff[MAXN];

int main()

{

        //freopen("input.txt","r",stdin);

        int n,x,y;

        scanf("%d",&n);

        int i,j,k,ii;

        qword ans=;

        memset(ff,-,sizeof(ff));

        for (i=;i<;i++)

        {

                if ((<<i)<MAXN)

                        ff[(<<i)]=i;

        }

        for (i=;i<MAXN;i++)

                if (ff[i]==-)ff[i]=ff[i-];

        for (ii=;ii<=n;ii++)

        {

                if (ii%== || ii%==)continue;

                int l,r,mid;

                l=,r=;

                while (l+<r)

                {

                        mid=(l+r)>>;

                        if ((qword)ii*pow(,mid)<=n)

                                l=mid;

                        else

                                r=mid;

                }

                memset(dp,,sizeof(dp));

                dp[][]=;

                x=ii;

                for (i=;ii*(<<i>>)<=n;i++)//log(n)

                {

                        for (j=;j<(<<r);j++)//2^(log3(n))

                        {

                                if (!dp[i-][j])continue;

                                for (k=;k<(<<r);k++)

                                {

                                        if (j&k || (k&(k<<)))continue;

                                        if ((qword)x*pow(,ff[k])>n)break;

                                        dp[i][k]=(dp[i][k]+dp[i-][j])%MOD;

                                }

                        }

                        x*=;

                }

                qword res=;

                for (j=;j<(<<r);j++)

                {

                        res=(res+dp[i-][j])%MOD;

                }

                ans=ans*res%MOD;

        }

        printf("%lld\n",ans);

}

码农公寓