P8292 [省选联考 2022] 卡牌（官方数据） 题解

~~时间复杂度理论都白学了系列~~ 可能随着评测机越来越快$O(nm)$能通过的数据极限也在增长吧…… 前几年觉得5000×5000就有点悬了现在8000×18000也变成随便过了…… ____________________________ ### 前置芝士:容斥原理 如果不会容斥原理的话可以做一做[这道题](https://www.luogu.com.cn/problem/P3349)学习一下。 这道题用的是最经典的容斥原理:如果我们想算合法方案总数，其中每一个合法方案需要满足n条限制。那么我们就先算出随便取的方案数（打破0条限制），然后减去打破一条限制的方案数，加上打破两条限制的方案数……这样把打破0~n条限制的方案数放在一起加加减减就能得到总方案数。 ## 本题题解 ### 从朴素的容斥开始 整理一下题意就是:给定$n$张写着数字的卡片，多次询问，每次询问给出一个大小为$c$的质数的集合$T=\{p_{1},p_{2} \dots p_{c}\}$，求有多少种选取卡片的方法，使得每一个在$T$中出现的质数$p_{i}$都是被选中的卡片上数字之乘积$Q$的约数。 相当于有$c$条限制，第$i$条限制就是“选择的数字中至少有一个是$p_{i}$的倍数”。打破这条限制就变成了“不能选择$p_{i}$的倍数”。 那么我们就可以根据容斥原理列出一个朴素的式子： $$Ans=\sum_{P \subseteq T }(-1)^{|P|}2^{cnt(P)}$$ 其中$cnt(P)$表示上面的数字不是$P$中任意一个质数的倍数的卡片张数。 这个式子的意义就是先枚举要打破的限制集合$P$。 为了打破集合中的限制我们就只能在$cnt(P)$张卡片中自由选择，所以方案数就是$2^{cnt(p)}$。 $(-1)^{|P|}$则是容斥系数。 ### 分类讨论 不过直接这么做复杂度是指数级别的，肯定过不去，所以我们还需要找点别的性质。 注意到数字的值域很小，只有$2000$。 通过打表我们发现$43×47=2021,43×41=1763$,这说明一个数字**不可能有两个不同的大于等于$43$的质因子**。 $2000$以内的质数有$303$个，而小于$43$的质数只有$13$个。 $13$的确是个令人心动的小数字，我们可以围绕它搞各种各样的暴力，比如状压。 于是我们将质数分为两个集合$A,B$。集合$A$中是大于等于$43$的质数，而集合$B$中则是小于$43$的质数。 设$T_{A}=T \cap A,T_{B}=T \cap B$，重新写一次之前的容斥式子： $$Ans=\sum_{P_{B}\subseteq T_{B}}\sum_{P_{A} \subseteq T_{A}}(-1)^{|P_{B} \cup P_{A}|}2^{cnt(P_{B} \cup P_{A})}$$ 做一点小小的整理: $$Ans=\sum_{P_{B}\subseteq T_{B}}\sum_{P_{A} \subseteq T_{A}}(-1)^{|P_{B}| + |P_{A}|}2^{cnt(P_{B} \cup P_{A})}$$ $$Ans=\sum_{P_{B}\subseteq T_{B}}(-1)^{|P_{B|}}\sum_{P_{A} \subseteq T_{A}}(-1)^{|P_{A}|}2^{cnt(P_{B} \cup P_{A})}$$ ### 计算$cnt(P_{B} \cup P_{A})$ 那么现在我们需要计算$cnt(P_{B} \cup P_{A})$，有没有什么简单的方法计算它呢？ 不要忘了每个数字最多含有一个$A$中的质因子，由此我们可以通过枚举A中的质因子$i$来计算$cnt(P_{B} \cup P_{A})$: $$cnt(P_{B} \cup P_{A})=\sum_{i \in A,i \notin P_{A}}newcnt( P_{B},i)$$ 其中$newcnt(P_{B},i)$表示符合以下条件的卡牌张数: 1.卡牌上的数字在$A$中的质因子恰好为$i$。 2.这个数字不是$P_{B}$中任何一个质数的倍数。 不过上面的式子有一点小锅，就是没有处理这个数字没有在$A$中的质因子的情况。 解决方法也很简单，把这个数字的$i$值钦定为$0$,再强行把$0$塞到$A$里去，我们的式子就又成立了。 $newcnt(P_{B},i)$的总状态量只有$2^{13}×290$,因此可以在$O(2^{13}\max{S_{i}})$的时间内预处理出来。 ### 推点式子 好了，现在我们把$cnt(P_{B} \cup P_{A})$代入到之前的式子里: $$Ans=\sum_{P_{B}\subseteq T_{B}}(-1)^{|P_{B|}}\sum_{P_{A} \subseteq T_{A}}(-1)^{|P_{A}|}2^{\sum_{i \in A,i \notin P_{A}}newcnt( P_{B},i)}$$ 把$\Sigma$从指数上拆下来变成$\Pi$: $$Ans=\sum_{P_{B}\subseteq T_{B}}(-1)^{|P_{B|}}\sum_{P_{A} \subseteq T_{A}}(-1)^{|P_{A}|}\prod_{i \in A,i \notin P_{A}}2^{newcnt( P_{B},i)}$$ 式子的后半部分还可以写成这样: $$\sum_{P_{A} \subseteq T_{A}}\prod_{i \in P_{A}}(-1)\prod_{i \in A,i \notin P_{A}}2^{newcnt( P_{B},i)}$$ 那其实就是这个式子的展开式: $$\prod_{i \in A}(2^{newcnt( P_{B},i)}-[i \in T_{A}])$$ 其中$[i \in T_{A}]$的值是1当且仅当$i \in T_{A}$，其他情况值为0。 解释一下这两个式子为什么相等:类似于二项式定理的证明，最后一个式子里面每个括号可以选$2^{newcnt( P_{B},i)}$或者$-1$。 选前者就认为这个元素不在$P_{A}$中，选后者就认为在$P_{A}$中，那么这些括号相乘的所有展开项就自动枚举了所有的$P_{A}$。由于不在$T_{A}$中的元素一定不在$P_{A}$中，所以需要用$[i \in T_{A}]$来限制范围。 那么现在我们的式子变成了这样: $$Ans=\sum_{P_{B}\subseteq T_{B}}(-1)^{|P_{B|}}\prod_{i \in A}(2^{newcnt( P_{B},i)}-[i \in T_{A}])$$ 提一个公因式: $$Ans=\sum_{P_{B}\subseteq T_{B}}(-1)^{|P_{B|}}\prod_{i \in A}2^{newcnt( P_{B},i)}\prod_{i \in T_{A}}(1-2^{-newcnt(P_{B},i)})$$ 简单分析一下暴力算上面式子的复杂度。 $1-2^{-newcnt(P_{B},i)}$和$\prod_{i \in A}2^{newcnt( P_{B},i)}$都能在$O(2^{13}\max{S_{i}})$的时间内预处理，复杂度不是问题。 预处理之后回答一次询问的复杂度是$O(2^{|T_{B}|}|T_{A}|)$的。 所以回答的总复杂度就是$O(2^{13}\Sigma c_{i})$的。 总复杂度高达$8192×18000$，我也不知道是评测机速度提起来了还是没跑满，总之直接过去了……。 ~~算了，复杂度就图一乐，过题还得看信仰。~~ 上代码~ ```cpp #include<cstdio> #include<algorithm> #include<set> using namespace std; const int N=2010; typedef long long ll; const ll mod=998244353; const int MXB=4096*2; ll po(ll a,ll p)//快速幂 { ll r=1; for(;p;p>>=1,a=a*a%mod) if(p&1)r=r*a%mod; return r; } ll mi2[9000]; int siz[9000]; ll f[9000][N];//1 -2^(-newcnt) ll mul[9000]; ll cnta[N]; int pb[N]; int pa[N]; int mindiv[N]; bool ta[N]; int q[N];int hd; //调试用的宏 # define prita(a,n)\ printf(#a":");for(int i=0;i<=n;i++)printf("%lld ",a[i]);printf("\n"); int main() { siz[0]=0; for(int i=1;i<=MXB;i++)siz[i]=siz[i>>1]^((i&1)); mi2[0]=1; for(int i=1;i<N-5;i++)mi2[i]=mi2[i-1]*2%mod; for(int i=1;i<N-5;i++)mindiv[i]=i; for(int i=2;i<N-5;i++) for(int j=i+i;j<N-5;j+=i) //处理每个数字的最小约数（也是最小质因子) mindiv[j]=min(mindiv[j],i); int tot=0; //处理出每个数字的A集合和B集合 for(int i=2;i<N-5;i++) { if(mindiv[i]==i)//质数的情况 { if(i<43) { pb[i]=1<<tot,tot++; } else { for(int j=i;j<N-5;j+=i) pa[j]=i; } } else //非质数的情况除掉最小质因子递归 { pb[i]=pb[i/mindiv[i]]|pb[mindiv[i]]; } } int n; scanf("%d",&n); int mxs=0; for(int i=1;i<=n;i++) { int s;scanf("%d",&s); cnta[s]++; mxs=max(mxs,s); } for(int s=0;s<MXB;s++)mul[s]=1; for(int i=1;i<=mxs;i++) { for(int s=MXB-1;s>=0;s--) if((s&pb[i])==0)//计算newcnt { f[s][pa[i]]+=cnta[i]; } } for(int i=0;i<=mxs;i++) if(i==pa[i])//根据newcnt计算需要预处理的两个数组。 { for(int s=0;s<MXB;s++) { //这里f的定义发生了改变，从newcnt变成了1-2^(-newcnt) f[s][i]=po(2,f[s][i])%mod; (mul[s]*=f[s][i])%=mod; f[s][i]=(1+mod-po(f[s][i],mod-2))%mod; } } int m; scanf("%d",&m); for(int i=1;i<=m;i++) { int c; scanf("%d",&c); int tb=0; hd=0; for(int j=1;j<=c;j++) { int p; scanf("%d",&p); if(p<43) { tb|=pb[p]; } else { if(ta[p]==false)q[++hd]=p; ta[p]=true; } } for(int i=1;i<=hd;i++)ta[q[i]]=false; //计算tb,ta,ta存到了数组q里。 ll ans=0; for(int sb=tb;1;sb=(sb-1)&tb)//枚举子集根据式子计算 { ll ret; if(siz[sb])ret=mod-mul[sb]; else ret=mul[sb]; for(int j=1;j<=hd;j++) (ret*=f[sb][q[j]])%=mod; (ans+=ret)%=mod; if(sb==0)break; } printf("%lld\n",ans); } return 0;//拜拜程序~ } ```