发现了栀子的一首歌 Go crazy for me,真上头。
昨天有一根木刺扎进了我右手中指,伤口愈合后挑不出来了,写代码按到那里就会痛一下。
匈牙利跑二分图匹配可以找到增广路后再清空 vis 数组,某些题中会有优越性。(反正不劣)
做了 CF848D Shake It!,觉得挺简单,就不记录了。
CF1726G A Certain Magical Party,sb 结论题,还不会做。
称数列中没有其真因子的数为好数,调整可知每次使用的 \(a_i\) 都可以是好数。
我们可以丢掉 \(>\lfloor\frac m2\rfloor\) 的好数,于是有用的好数不会超过 \(\lfloor\frac m4\rfloor\) 个,可以状压。
具体地,我们可以将好数分成若干个互不影响的集合再乘上归并的系数,现只考虑一个内部有影响的好数集合。更严谨的说法是,将好数与其倍数连边生成一个二分图,我们分连通块考虑。
可以发现这个连通块最多删右部点数量减一个数,同时这也可以达到。于是我们只需求“初始右部只有一个点激活,按照规则激活右部所有点的方案数”。
对左部点状压,一个直觉的 dp 是 \(f_{S,i}\) 表示左部集合为 \(S\),右部选了 \(i\) 个点的方案数,复杂度 \(O(2^\frac{m}{4}n^2)\),已经可以通过。
类似 AT5042 Edge Ordering,我们可以将状态去除第二维,将其改为“左部集合为 \(S\),且已经计算完仅连向 \(S\) 补集的右部点的贡献”,每次删除一个数也是归并的形式,可以直接计算。
复杂度 \(O(2^\frac m4n^2)\)。
#include<stdio.h> #include<assert.h> const int maxn=65,mod=1000000007,maxt=1<<15; int n,ans,ids,sum; int a[maxn],gd[maxn],fac[maxn],nfac[maxn],S[maxn],id[maxn],T[maxt],dsu[maxn],g[maxn],f[maxt],h[maxn]; int find(int x){ return dsu[x]==x? x:dsu[x]=find(dsu[x]); } int ksm(int a,int b){ int res=1; while(b){ if(b&1) res=1ll*res*a%mod; a=1ll*a*a%mod,b>>=1; } return res; } int main(){ fac[0]=nfac[0]=1; for(int i=1;i<=60;i++) fac[i]=1ll*fac[i-1]*i%mod,nfac[i]=ksm(fac[i],mod-2); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),dsu[i]=i; for(int i=1;i<=n;i++){ gd[i]=a[i]<=30; for(int j=1;j<=n;j++) gd[i]&=(i==j||a[i]%a[j]!=0); if(gd[i]){ id[i]=++ids; for(int j=1;j<=n;j++) if(i!=j&&a[j]%a[i]==0) S[j]|=(1<<(ids-1)),dsu[find(j)]=find(i); } } ans=1; for(int t=1;t<=n;t++) if(dsu[t]==t){ int c=0,s=0,cnt=0; for(int i=1;i<=n;i++) if(find(i)==t){ if(gd[i]) g[++c]=i,s|=g[c]; else h[++cnt]=i; } if(s==0||cnt==0) continue; for(int i=1;i<=cnt;i++){ S[i]=0; for(int j=1;j<=c;j++) if(a[h[i]]%a[g[j]]==0) S[i]|=(1<<(j-1)); T[S[i]]++; } for(int i=0;i<c;i++) for(int j=0;j<(1<<c);j++) if((j>>i)&1) T[j]+=T[j^(1<<i)]; f[(1<<c)-1]=1; for(int i=(1<<c)-2;i>=0;i--){ for(int j=1;j<=cnt;j++) if(i==0||(i&S[j])>0){ int nxt=i|S[j]; if(nxt>i) f[i]=(f[i]+1ll*f[nxt]*fac[cnt-T[i]-1]%mod*nfac[cnt-T[nxt]])%mod; } } ans=1ll*ans*nfac[cnt-1]%mod*f[0]%mod,sum+=cnt-1; for(int i=0;i<(1<<c);i++) f[i]=T[i]=0; } printf("%d\n",(int)(1ll*fac[sum]*ans%mod)); return 0; }