自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 22:27:51，当前版本为作者最后更新于2021-01-28 20:02:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析 + 题解

正难则反，题目需要求有几个子集的元素积 $>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$，所以也可以采用一乘一除的方式求组合数：