CF1292F Nora's Toy Boxes

· · 题解

CF1292F

第一步先模型转化并得出最多能删多少个数（解决第一问）。

如果 x | y 那么我们连边 x\to y。对每个弱连通块考虑计算能删多少个数。

手玩一下会发现，能删的个数为 入度不为 0 的点的个数 减一。

接下来考虑第二问的计数。

这个 n,a_i\le 60 看起来很迷惑，但我们仔细分析一下。

显然，入度为 0 的点是用来删除别的数的。

我们把删点改成加点，并且一开始就有一个点（因为前面说 能删的个数为 入度不为 0 的点的个数 减一）。

那么此时入度为 0 的点是用来加入别的数的，并且对于一个入度为 0 的点 x，必须已经有一个加入的点 y 使得有边 x\to y，才能加一个点 z（有边 x\to z）

此时就有思路了，对于一个入度为 0 的点 x，如果图上已经有了一个 x\to y，那么 x 就被激活了，可以用来加别的点。

考虑状压入度为 0 的点被激活的状态，然后就能加点 DP 了。

对于每个联通块，入度为 0 ，并且有出边的点一定只能是 1\sim 30，并且选了一个点入度为 0 ，它的倍数就不能选。所以最多形成了 1\sim 30 的最长反链，入度为 0 的个数一定 \le 15，所以可以状压。

设 f(i,S) 表示加入了 i 个点，被激活的状态为 S。设 cnt_S 表示 S 能加的点个数。

然后如果不改变激活状态可以乘上系数 cnt_S - i；如果改变了激活状态，枚举下一个加的点并转移。

复杂度就是 O(2^{15}\times n^2)。

在 这里 看到了另一个有趣的做法。

对于入度不为 0 的点，如果存在 a_i|a_j,a_i|a_k 就把 j,k 连起来，得到一张可能删掉的点的图。

考虑给这些可能删掉的点标删除顺序的标号，要保证除了最大的以外，其他每个点都至少有一个相邻点标号大于它，标号的方案数就是答案。

可以容斥，钦定若干个点的标号大于相邻的，然后从小到大填标号，状压 DP 。

这个状压 DP 的状态也只有 2^{\text{入度为 0 的个数}}，因为状态一定是几个 入度为 0 的个数 能到达的点 的并集，于是复杂度是对的。

下面是第一种做法的代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
    if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
    int m=iv.size(); ++n;
    if(m>=n)return;
    iv.resize(n),fac.resize(n),ifac.resize(n);
    For(i,m,n-1){
        iv[i]=iv[mod%i]*(mod-mod/i);
        fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
    }
}
inline modint C(int n,int m){
    if(m<0||n<m)return 0;
    return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int n,m,a[66],in[66];
modint res=1;
modint dp[63][1<<15];
int sum,col[66],now,p[66];
bool vis[66];

int tot,tot0,val[66],cnt[1<<15];

void dfs(int u){
    if(col[u]==now)return;
    col[u]=now;++tot;
    For(v,1,n) if(a[u]%a[v]==0||a[v]%a[u]==0) dfs(v);
}

signed main()
{
    n=read(),initC(60);
    For(i,1,n)a[i]=read();
    For(i,1,n)
        For(j,1,n)
            if(i!=j&&a[i]%a[j]==0)++in[i]; // a[j]|a[i] j->i
    For(u,1,n)
    {
        if(col[u])continue;
        ++now,tot=tot0=0,dfs(u);
        For(i,1,n)
            if(col[i]==now && !in[i]) vis[i]=1,p[tot0++]=a[i];
        if(tot-tot0<=1) continue;

        int mxs=(1<<tot0);
        For(i,0,n)For(s,0,mxs-1)dp[i][s]=0;
        memset(cnt,0,sizeof cnt);

        For(i,1,n)
            if(!vis[i] && col[i]==now){
                For(j,0,tot0-1)
                    if(a[i]%p[j]==0) val[i]|=(1<<j);
                dp[1][val[i]]+=1;
                For(s,0,mxs-1)
                    if((s&val[i])==val[i])
                        cnt[s]++;
            }

    //  For(i,1,n) if(!vis[i] && col[i]==now) cout<<val[i]<<' '; puts("");
    //  For(s,0,mxs-1) cout<<cnt[s]<<' '; puts("");

        For(i,1,tot-tot0-1)
            For(s,0,mxs-1){
                if(!dp[i][s].x) continue;
                if(cnt[s]>i)
                    dp[i+1][s]+=dp[i][s]*(cnt[s]-i);
                For(j,1,n)
                    if(col[j]==now && !vis[j] && ((s|val[j])>s) && (s&val[j]))
                        dp[i+1][s|val[j]]+=dp[i][s];
            }
        modint ans=0;
        For(s,0,mxs-1)
            ans+=dp[tot-tot0][s];
        sum+=tot-tot0-1;
        res=res*ans*ifac[tot-tot0-1];
    }
    res=res*fac[sum];
    cout<<res.x;
    return 0;
}