「CF1292F」Nora's Toy Boxes

「CF1292F」Nora's Toy Boxes

九月 15, 2020 · OI 题解

一个大小为 $n$ 的集合 $\{a_i\}_{i=1}^n$，每次可以选择 $(i,j,k)$，若 $a_i \mid a_j$ 且 $a_i \mid a_k$，可以将 $a_k$ 删去。

求能删除最多数的删除序列数，删除序列定义为对于一个三元组 $(i,j,k)$，每次删数把 $a_k$ 加入到删除序列中。

$1 \leq a_i, n \leq 60$，保证 $a_i$ 两两不同。

题解

考虑如果 $a_i \mid a_j$，就从 $i$ 到 $j$ 连一条边，这样形成的图是一个偏序集。不妨只考虑第一层的点，称为 $A$ 类点，其余的点称为 $B$ 类点。每次删除操作可以转化为，找到一个 $A$ 类点，存在 $\geq 2$ 的出度，就可以删掉其中任意一条出边指向的点。

对于任意一个由 $A$、$B$ 类点组成的非平凡弱联通块，一定存在一种删除方式使得是剩下其中的 $A$ 类点和某一个 $B$ 类点。这就是删除最多数的方案。

那么怎么统计方案数呢，我们枚举最后剩下的点，然后把删除操作倒过来做，变成加入操作。那么我们可以状压一个状态，是一个 $A$ 类点的集合，此时这些 $A$ 类点有至少 $1$ 的出度。那么每次被反向「删除」回来的点一定和状态中的某一个 $A$ 类点有边，且会产生两种影响，即：要么增加后状态不变，要么增加后使得更多的 $A$ 类点变成「可用」。

我们不妨在每次导致第二种影响的时候统计方案，就不会统计重复，这样的话可以得到一个 $O(2^{r} n^2)$ 的暴力 DP，其中 $r$ 是 $A$ 类点的个数。

如果我们删除没有出度的点，容易证明 $r \leq 15$（$[16,30] \cup [46,60]$），可以通过本题。实际上如果特判出度为 $1$，能让 $r$ 做到更小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
const int N=65,mod=1e9+7;
int n,m,tot,sum,ans,in[N],out[N],anc[N],val[N],tag[N],fac[N],ifac[N],S[1<<15],dp[N][1<<15];
long long T[1<<15];
int find(int x){return anc[x]==x?x:anc[x]=find(anc[x]);}
inline int C(int n,int m){return n<m?0:(long long)fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
int main(){
#ifdef memset0
  freopen("1.in","r",stdin);
#endif
  fac[0]=ifac[0]=ifac[1]=1;
  for(int i=2;i<N;i++)ifac[i]=(long long)(mod-mod/i)*ifac[mod%i]%mod;
  for(int i=1;i<N;i++)fac[i]=(long long)fac[i-1]*i%mod,ifac[i]=(long long)ifac[i-1]*ifac[i]%mod;
  cin>>n;
  for(int i=1;i<=n;i++)cin>>val[i],tag[val[i]]=true;
  m=*std::max_element(val+1,val+n+1);
  for(int i=1;i<=m;i++)if(tag[i])anc[i]=i;
  for(int i=1;i<=m;i++)if(tag[i])
    for(int j=(i<<1);j<=m;j+=i)if(tag[j]){
      out[i]++,in[j]++;
      anc[find(i)]=find(j);
    }
  ans=1;
  // for(int i=1;i<=m;i++)printf("%d%c",tag[i]?find(i):-1," \n"[i==m]);
  for(int c=1;c<=m;c++)if(tag[c]&&find(c)==c){
    std::vector<int> a,b;
    std::vector<long long> A,B;
    for(int i=1;i<=m;i++)if(tag[i]&&find(i)==c){
      if(!in[i]){
        if(!out[i])continue;
        a.push_back(i);
      }else{
        b.push_back(i);
      }
    }
    if(!b.size())continue;
    A.resize(a.size());
    B.resize(b.size());
    for(int i=0;i<a.size();i++)
      for(int j=0;j<b.size();j++)
        if(b[j]%a[i]==0){
          A[i]|=1ll<<j;
          B[j]|=1ll<<i;
        }
    for(int x=0;x<(1<<a.size());x++){
      long long s=0,t=0;
      for(int i=0;i<a.size();i++)if((x>>i)&1)t|=A[i];
      for(int j=0;j<b.size();j++)if(((t>>j)&1)&&(x&B[j])==B[j])s|=1ll<<j;
      S[x]=__builtin_popcountll(s),T[x]=t;
    }
    sum=0;
    for(int i=0;i<b.size();i++){
      for(int i=0;i<=b.size();i++)memset(dp[i],0,(1<<a.size())<<2);
      dp[1][B[i]]=fac[S[B[i]]-1];
      for(int x=B[i],y;x<(1<<a.size());x++)
        for(int t=0;t<b.size();t++)if(((T[x]>>t)&1)&&(y=x|B[t])!=x)
          for(int i=1;i<b.size();i++)if(dp[i][x])
            for(int j=i+1;j<=b.size();j++){
              // printf("%d %d %d[%d] : %d(%d) -> %d(%d)\n",i,j,t,b[t],x,S[x],y,S[y]);
              dp[j][y]=(dp[j][y]+(long long)dp[i][x]*C(S[y]-j,S[y]-S[x]-1)%mod*fac[S[y]-S[x]-1])%mod;
            }
      for(int i=0;i<=b.size();i++)sum=(sum+dp[i][(1<<a.size())-1])%mod;
      // printf("%d[%d] %d\n",i,b[i],sum);
    }
    // for(int i=0;i<a.size();i++)printf("%d,%lld%c",a[i],A[i]," \n"[i+1==a.size()]);
    // for(int i=0;i<b.size();i++)printf("%d,%lld%c",b[i],B[i]," \n"[i+1==b.size()]);
    tot+=b.size()-1;
    ans=(long long)ans*sum%mod*C(tot,b.size()-1)%mod;
    // printf(">> %d %d\n",(int)b.size(),sum);
  }
  cout<<ans<<endl;
}