P3226 [HNOI2012]集合选数[DP]【-11】

2018-04-03

题目描述

《集合论与图论》这门课程有一道作业题，要求同学们求出{1, 2, 3, 4, 5}的所有满足以下条件的子集：若 x 在该子集中，则 2x 和 3x 不能在该子集中。

同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 n<=100000，如何求出{1, 2,…, n} 的满足上述约束条件的子集的个数（只需输出对 1,000,000,001 取模的结果），现在这个问题就交给你了。

输入输出格式

输入格式：

只有一行，其中有一个正整数 n，30%的数据满足 n<=20。

输出格式：

仅包含一个正整数，表示{1, 2,…, n}有多少个满足上述约束条件的子集。

输入输出样例

输入样例#1：

输出样例#1：

【样例解释】

有8 个集合满足要求，分别是空集，{1}，{1，4}，{2}，{2，3}，{3}，{3，4}，{4}。

题解

列一个矩阵

1	3	9	27
2	6	18	54
4	12	36	108
8	24	72	216

（i，j）的数是（i，j-1）的三倍，（i-1，j）的两倍

可以通过第一列看出，10w以内这样的表格，不会超过17行/列。

于是可以状压dp了。相当于取了某个数，该数上下左右的都不能取。

然而还剩了一些数qaq，剩下的数就重新列个表来dp。

我的复杂度有点萎，还T过来着，然后卡了下常。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
    char s;
    int k=0,base=1;
    while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if(s==EOF)exit(0);
    if(s=='-')base=-1,s=getchar();
    while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
    return k*base;
}
inline void write(int x)
{
    static char cnt,num[15];cnt=0;
    if (!x)
    {
        printf("0");
        return;
    }
    for (;x;x/=10) num[++cnt]=x%10;
    while (cnt<5) cnt++,num[cnt]=0;
    for (;cnt;putchar(num[cnt--]+48));
}
const int maxn=1e5+400;
const ll mod=1000000001;
const int N=1e5;
int n,X,Y,vis[maxn];
int a[20][20],cnt;
ll ans,sum;
int Map[1<<18],ma[6770],f[2][6770];
vector<int> G[6770];
int main()
{
    n=read();ans=1;
    for (int i=0;i<(1<<18);i++)
    {
        if (i>=(n*2)) break;
        if (!(i&(i<<1))&&(!(i&(i>>1))))
        {
            cnt++;
            ma[cnt]=i;
            Map[i]=cnt;		
        }
    }
    G[1].push_back(1);
    for (int i=1;i<=cnt;i++)
    {
        if (ma[i]>n*2) break;
        for (int j=i+1;j<=cnt;j++)
        {
            if (ma[j]>n*2) break;
            if (!(ma[i]&ma[j]))
            {
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }//存下合法的转移
    for (int T=1;T<=n;T++)
    {
        if (vis[T]) continue;
        sum=0;
        memset(a,0,sizeof(a));
        vis[T]=1;a[1][1]=T;X=1;Y=1;
        for (int i=1;;i++)
        {
            if (i!=1) a[i][1]=a[i-1][1]*2;
            if (a[i][1]>n) {a[i][1]=0;X=i-1;break;}
            vis[a[i][1]]=1; 
            for (int j=2;;j++)
            {
                a[i][j]=a[i][j-1]*3;
                if (a[i][j]>n) {a[i][j]=0;a[i][0]=j-1;qmax(Y,j-1);break;}
                vis[a[i][j]]=1;
            }
        }//暴力求出矩阵（emmm应该是暴力打标记，求出来并没有什么用
        if (X==1&&Y==1) 
        {
            ans=ans+ans;
            if (ans>=mod) ans-=mod;
            continue;
        }
        memset(f,0,sizeof(f));
        f[0][1]=1;
        for (int i=1;i<=X;i++)
        {
            memset(f[i&1],0,sizeof(f[i&1]));
            for (int j=1;j<=cnt;j++)//枚上一行状态
            {
                if (ma[j]>=((1<<(a[i-1][0])))) break;//越界了
                int Size=G[j].size()-1;
                for (int k=0;k<=Size;k++)//转移
                {
                    if (ma[G[j][k]]>=((1<<(a[i][0])))) break;
                    f[i&1][G[j][k]]+=f[(i-1)&1][j];
                    if (f[i&1][G[j][k]]>=mod) f[i&1][G[j][k]]-=mod;
                }
            } 
        }
        for (int i=1;i<=(1<<a[X][0]);i++) 
        { 
            sum+=f[X&1][i];
            if (sum>=mod) sum-=mod;
        }
        ans=ans*sum%mod;
    }
    printf("%lld\n",ans);
    return 0;
}