shadowice1984 的博客

shadowice1984 的博客

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

posted on 2022-04-22 01:34:33 | under 题解 |

时间复杂度理论都白学了系列

可能随着评测机越来越快$O(nm)$能通过的数据极限也在增长吧……

前几年觉得5000×5000就有点悬了现在8000×18000也变成随便过了……


前置芝士:容斥原理

如果不会容斥原理的话可以做一做这道题学习一下。

这道题用的是最经典的容斥原理:如果我们想算合法方案总数,其中每一个合法方案需要满足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$,我也不知道是评测机速度提起来了还是没跑满,总之直接过去了……。

算了,复杂度就图一乐,过题还得看信仰。

上代码~


#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;//拜拜程序~    
}