[BZOJ2734/Luogu3226][HNOI2012]集合选数(状态压缩动态规划,构造)

发布于 2018-03-29  60 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2734/Luogu3226][HNOI2012]集合选数(状态压缩动态规划,构造)

Description

《集合论与图论》这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集:若 x 在该子集中,则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目,于是把它变成了以下问题:对于任意一个正整数 n≤100000,如何求出{1, 2,..., n} 的满足上述约束条件的子集的个数(只需输出对 1,000,000,001 取模的结果),现在这个问题就 交给你了。

Tag

状态压缩动态规划,构造

解决思路

构造一个矩阵,左上角是1,接下来每一个数是它左边的数的2倍,上面的数的3倍。这样问题转化为在矩阵中选择若干个不相邻的方案数。
由于是乘法,矩阵的长宽都是\(log\)级别的,所以可以状态压缩动态规划求解 。
但是可以发现,有一些数是没有出现在这个矩阵中的,所以我们再选择一个没有在矩阵中出现的最小的数,作为新的矩阵的左上角,再进行动态规划。直到所有数都在矩阵中出现过。由于各矩阵是互相独立的,所以是把方案数相乘。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int maxMap=18;
const int Mod=1000000001;
const int inf=2147483647;

int n;
bool Used[maxN];
int Len[maxMap];
int Map[maxMap][maxMap];
int F[maxMap][1<<maxMap];

ll Calc(int st);

int main()
{
    ios::sync_with_stdio(false);

    ll Ans=1;
    cin>>n;
    for (int i=1;i<=n;i++) if (Used[i]==0) Ans=Ans*Calc(i)%Mod;//枚举没有出现的数
    cout<<Ans<<endl;

    return 0;
}

ll Calc(int st)
{
    //构造矩阵
    Used[Map[1][1]=st]=1;
    for (int i=2;;i++)
    {
        if (Map[1][i-1]*3ll>n){
            Len[1]=i-1;break;
        }
        Used[Map[1][i]=Map[1][i-1]*3ll]=1;
    }
    int line;
    for (int i=2;;i++)
    {
        if (Map[i-1][1]*2ll>n){
            line=i-1;break;
        }
        Used[Map[i][1]=Map[i-1][1]*2ll]=1;
        for (int j=2;;j++)
        {
            if (Map[i][j-1]*3ll>n){
                Len[i]=j-1;break;
            }
            Used[Map[i][j]=Map[i][j-1]*3]=1;
        }
    }
    //状压求解
    for (int i=1;i<=line;i++) for (int S=0;S<(1<<Len[i]);S++) F[i][S]=0;
    F[0][0]=1;
    for (int S=0;S<(1<<Len[1]);S++)
        if ((S&(S<<1))==0) F[1][S]=1;
    for (int i=2;i<=line;i++)
    {
        for (int S1=0;S1<(1<<Len[i-1]);S1++)
            if ((S1&(S1<<1))==0)
                for (int S2=0;S2<(1<<Len[i]);S2++)
                    if (((S2&(S2<<1))==0) && ((S1&S2)==0))
                        F[i][S2]=(F[i][S2]+F[i-1][S1])%Mod;
    }
    ll Ret=0;
    for (int S=0;S<(1<<Len[line]);S++)
        if ((S&(S<<1))==0) Ret=(Ret+F[line][S])%Mod;
    return Ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2734/Luogu3226][HNOI2012]集合选数(状态压缩动态规划,构造)


HNCJ OIer