「题解」付公主的背包

付公主的背包 ，一道 生成函数 题。

题目链接：Luogu P4389。

题目

题目描述

这个背包最多可以装 \(10^5\) 大小的东西。

付公主有 \(n\) 种商品，她要准备出摊了。

每种商品体积为 \(v _ i\)，都有无限件。

给定 \(m\)，对于 \(s\in[1,m]\)，请你回答用这些商品恰好装 \(s\) 体积的方案数，答案对 \(998244353\) 取模。

数据范围

对于 \(30\%\) 的数据，\(1\leq n,m\leq 3000\)；
对于 \(60\%\) 的数据，纯随机生成；
对于 \(100\%\) 的数据，\(1\leq n,m\leq 10^5,1\leq v _ i\leq m\)。

时空限制

题目编号	时间限制	空间限制
Luogu P4389	\(1\text{s}\)	\(500\text{MiB}\)

题解

付公主的背包 ，一道 生成函数 题。

前置知识

• 「OI」生成函数 Generating Function；
• 多项式 \(\texttt{exp}\)。

思路

直接用 生成函数 来描述答案。写出答案的式子。
\[\texttt{ans}(x)=\prod^n _ {i=1}(\sum _ jx^{jv _ i})\]

然后取对数再求指数
\[\texttt{ans}(x)=e^{\ln(\prod^n _ {i=1}(\sum _ jx^{jv _ i}))}\]

主要关注指数上面的东西，我们不妨设它为 \(g(x)\)。
\[
\begin{aligned}
g(x)&=\ln(\prod^n _ {i=1}(\sum _ jx^{jv _ i}))\\
&=\sum^n _ {i=1}\ln(\sum _ jx^{jv _ i})\\
&=\sum^n _ {i=1}\ln\frac{1}{1-x^v}\\
&=\sum^n _ {i=1}\sum _ j\frac{x^{jv _ i}}{j}
\end{aligned}
\]

所以只要求出 \(g(x)\) 再套一个 \(\texttt{exp}\) 即可。

时间复杂度为 \(\Theta(n\log _ 2n+m\ln m)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int p=998244353;
const int g=3;
const int invg=332748118;

inline int pow(reg int x,reg int exp,reg int mod){
	reg int res=1;
	while(exp){
		if(exp&1)
			res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		exp>>=1;
	}
	return res;
}

const int MAXSIZE=800000+5;

namespace Poly{
	int inv_[MAXSIZE];
	inline void Init(void){
		inv_[1]=1;
		for(reg int i=2;i<MAXSIZE;++i)
        	inv_[i]=1ll*(p-p/i)*inv_[p%i]%p;
	}
	int r[MAXSIZE];
	inline int Init(const int len){
		reg int limit=1,l=0;
		while(limit<len)
			limit<<=1,++l;
		for(reg int i=1;i<limit;++i)
			r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
		return limit;
	}
	inline void diff(reg int res[],const int f[],const int n){
		for(reg int i=0;i<n-1;++i)
			res[i]=1ll*f[i+1]*(i+1)%p;
		return;
	}
	inline void sum(reg int res[],const int f[],const int n){
		for(reg int i=n;i>=1;--i)
			res[i]=1ll*f[i-1]*inv_[i]%p;
		res[0]=0;
		return;
	}
	inline void NTT(reg int a[],reg int limit,reg int type){
		for(reg int i=0;i<limit;++i)
			if(i<r[i])
				swap(a[i],a[r[i]]);
		for(reg int i=1;i<limit;i<<=1){
			reg int w=pow(type==1?g:invg,(p-1)/(i<<1),p);
			for(reg int j=0;j<limit;j+=(i<<1)){
				reg int e=1;
				for(reg int k=0;k<i;++k,e=1ll*e*w%p){
					reg int x=a[j+k],y=1ll*e*a[j+k+i]%p;
					a[j+k]=(x+y)%p,a[j+k+i]=(x-y+p)%p;
				}
			}
		}
		if(type==-1){
			reg int inv=pow(limit,p-2,p);
			for(reg int i=0;i<limit;++i)
				a[i]=1ll*a[i]*inv%p;
		}
		return;
	}
	inline int add(reg int a,reg int b,reg int mod){
		reg int sum=a+b;
		return sum>=mod?sum-mod:sum;
	}
	inline void add(reg int res[],const int a[],const int b[],reg int n){
		for(reg int i=0;i<n;++i)
			res[i]=add(a[i],b[i],p);
		return;
	}
	inline void mul(reg int res[],const int a[],const int la,const int b[],const int lb){
		static int A[MAXSIZE],B[MAXSIZE];
		reg int limit=Init(la+lb);
		for(reg int i=0;i<la;++i)
			A[i]=a[i];
		for(reg int i=la;i<limit;++i)
			A[i]=0;
		for(reg int i=0;i<lb;++i)
			B[i]=b[i];
		for(reg int i=lb;i<limit;++i)
			B[i]=0;
		NTT(A,limit,1),NTT(B,limit,1);
		for(reg int i=0;i<limit;++i)
			res[i]=1ll*A[i]*B[i]%p;
		NTT(res,limit,-1);
		for(reg int i=la+lb;i<limit;++i)
			res[i]=0;
		return;
	}
	inline void inv(reg int res[],const int f[],reg int n){
		if(n==1){
			res[0]=pow(f[0],p-2,p);
			return;
		}
		inv(res,f,(n+1)>>1);
		reg int limit=Init(n<<1);
		static int tmp[MAXSIZE];
		for(reg int i=0;i<n;++i)
			tmp[i]=f[i];
		for(reg int i=n;i<limit;++i)
			tmp[i]=0;
		NTT(tmp,limit,1),NTT(res,limit,1);
		for(reg int i=0;i<limit;++i)
			res[i]=1ll*(2ll-1ll*tmp[i]*res[i]%p+p)%p*res[i]%p;
		NTT(res,limit,-1);
		for(reg int i=n;i<limit;++i)
			res[i]=0;
		return;
	}
	inline void ln(reg int res[],const int f[],reg int n){
		static int df[MAXSIZE];
		static int invf[MAXSIZE];
		for(reg int i=0;i<n;++i)
			invf[i]=0;
		diff(df,f,n);
		inv(invf,f,n);
		mul(df,df,n-1,invf,n);
		sum(res,df,n);
		res[0]=0;
		return;
	}
	inline void exp(reg int res[],const int f[],reg int n){
		if(n==1){
			res[0]=1;
			return;
		}
		exp(res,f,(n+1)>>1);
		static int Ln[MAXSIZE];
		ln(Ln,res,n);
		reg int limit=Init(n<<1);
		for(reg int i=0;i<n;++i)
			Ln[i]=f[i]>=Ln[i]?f[i]-Ln[i]:f[i]-Ln[i]+p;
		for(reg int i=n;i<limit;++i)
			Ln[i]=res[i]=0; 
		++Ln[0];
		NTT(Ln,limit,1),NTT(res,limit,1);
		for(reg int i=0;i<limit;++i)
			res[i]=1ll*res[i]*Ln[i]%p;
		NTT(res,limit,-1);
		for(reg int i=n;i<limit;++i)
			res[i]=0;
		return;
	}
}

const int MAXN=100000+5;
const int MAXM=100000+5;

int n,m;
int cnt[MAXM];
int tmp[MAXSIZE];
int ans[MAXSIZE];

int main(void){
	Poly::Init();
	n=read(),m=read();
	for(reg int i=0;i<n;++i){
		static int v;
		v=read();
		++cnt[v];
	}
	for(reg int i=1;i<=m;++i)
		if(cnt[i])
			for(reg int j=i;j<=m;j+=i)
				tmp[j]=Poly::add(tmp[j],1ll*cnt[i]*i%p*Poly::inv_[j]%p,p);
	Poly::exp(ans,tmp,m+1);
	for(reg int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	return 0;
}