【题解】洛谷 P7224 [RC-04] 子集积

· · 题解

分析 + 题解

正难则反，题目需要求有几个子集的元素积 >m，我们将其转化为求有几个子集的元素积 \le m。（显然一共有 2^n 个子集）

很明显这是一个背包，考虑暴力加入每个物品，时间复杂度为 O(\sum_{i=1}^n \lfloor \dfrac{m}{a_i} \rfloor)。若 a_i 很小，则时间复杂度接近上界 O(nm)。

注意到若 a_i 互不相同，O(\sum_{i=1}^n \lfloor \dfrac{m}{a_i} \rfloor) \le O(\sum_{i=1}^m \dfrac{m}{i})=O(m \ln{m}) ，于是考虑将 a_i 相同的一起处理。

具体而言，设 a_i=j \; (j>1) 的 i 有 k 个，则使用 j,j^2,j^3,\cdots,j^k 进行转移，j^q 转移时系数为 (^k_q)。特别地，设a_i=1 的 i 有 k 个，则只需将最终答案乘以 2^k 而不作任何转移。

时间复杂度为 O(\sum_{i=2}^m \sum_{j=1}^{cnt_i} \lfloor \dfrac{m}{i^j} \rfloor)，由于总共只有不超过 n 项相加，且分母为指数级增长，所以可以将其近似的看成 O(m \ln{m})。（其中 cnt_i 表示值 i 的个数，n 和 m 同阶）

代码

预处理阶乘及其逆元用于求组合数，然后进行背包即可，代码其实很好写：

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
inline void add(int &a,int b)
{
    a=a+b-(a+b>=P?P:0);
}
inline void sub(int &a,int b)
{
    a=a-b+(a-b<0?P:0);
}
inline int get_pro(int a,int b)
{
    return 1ll*a*b%P;
}
/*以上为模意义下的运算*/
const int max_n=1e6+5;
int fac[max_n],inv[max_n],inv_fac[max_n];
inline void init(int n)//预处理阶乘 fac, 逆元 inv,以及阶乘的逆元 inv_fac 
{
    fac[0]=inv_fac[0]=1;
    fac[1]=inv[1]=inv_fac[1]=1;
    for(int i=2;i<=n;++i)
    {
        fac[i]=get_pro(fac[i-1],i);
        inv[i]=get_pro(P-P/i,inv[P%i]);
        inv_fac[i]=get_pro(inv_fac[i-1],inv[i]); 
    }
}
inline int C(int n,int m)//组合数 
{
    if(n<0||m<0||n<m)
        return 0;
    return get_pro(fac[n],get_pro(inv_fac[m],inv_fac[n-m]));
}
const int max_a=1e6+5;
int cnt[max_a];
const int max_m=1e6+5;
int dp[max_m];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        ++cnt[a];
    }
    int mx=0;
    for(int i=2;i<=1e6;++i)
        mx=max(mx,cnt[i]);
    init(mx);//只需预处理最大出现次数即可 
    dp[1]=1;
    for(int i=2;i<=1e6;++i)
    {
        if(cnt[i])//此处应判断是否有值为 i 的元素，否则会跑 m/i 长度的空循环 
        {
            for(int k=m/i;k>=1;--k)
            {
                if(dp[k])//有 dp 值才进行转移，减小常数 
                {
                    long long v=i;//注意 v 最大可能为 10^12，开 long long 
                    for(int j=1;j<=cnt[i]&&v*k<=m;++j,v*=i)
                        add(dp[v*k],get_pro(C(cnt[i],j),dp[k])); 
                }
            }
        }
    }
    int ans=1;
    for(int i=1;i<=n-cnt[1];++i)//ans=2^{n-cnt[1]} 
        add(ans,ans);
    for(int i=1;i<=m;++i)
        sub(ans,dp[i]);
    for(int i=1;i<=cnt[1];++i)//ans*=2^{cnt[1]} 
        add(ans,ans);
    printf("%d\n",ans);
    return 0;
}

PS：由于 \sum_{i=2}^m cnt_i \le n，所以也可以采用一乘一除的方式求组合数：

(^n_m)=\dfrac{n(n-1) \cdots (n-m+1)}{m!}