luoguP4389 付公主的背包

luogu

显然这是个背包题

显然物品的数量是不用管的

所以考虑大小为\(v\)的物品可以装的体积用生成函数表示一下

\[f(x)=\sum_{i=0}^{+\infty}x^{vi}=\frac{1}{1-x^v}\\
ans=\prod_{i=1}^{n}\frac{1}{1-x^{v_i}}
\]

然而这样直接乘起来复杂度是\(O(mn\ log\ n)\)

然后套路，左右套上\(ln\)就可以化乘为加

\[ln\ ans=\sum_{i=1}^{n}ln\ \frac{1}{1-x^{v_i}}
\]

把\(ln\)拆开

\[ln\ \frac{1}{1-x^v}=\int \frac{vx^{v-1}}{1-x^{v}}dx\\
ln\ \frac{1}{1-x^v}=\int \sum_{i=1}^{+\infty}vx^{vi-1}dx\\
ln\ \frac{1}{1-x^v}=\sum_{i=1}^{+\infty}\frac{1}{i}x^{vi}
\]

然后再求个exp就可以了

但是我们这样预处理最坏还是可以到\(O(n^2)\)，对于每个体积记个桶优化一下就可以了

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

void read(int &x) {

	char ch; bool ok;

	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

#define rg register

const int maxn=5e5+10,mod=998244353,g=3,gi=332748118;

int n,k,v[maxn],f[maxn],a[maxn],b[maxn],c[maxn],h[maxn],w[maxn],s[maxn],r[maxn],inv[maxn];

int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}

int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}

int del(int x,int y){return x-y<0?x-y+mod:x-y;}

int mi(int a,int b){

	int ans=1;while(b){if(b&1)ans=mul(ans,a);b>>=1,a=mul(a,a);}

	return ans;

}

void ntt(int *a,int n,int f){

	for(rg int i=0;i<n;i++)if(r[i]>i)swap(a[i],a[r[i]]);

	for(rg int i=1;i<n;i<<=1){

		int wn=mi(f?g:gi,(mod-1)/(i<<1));

		for(rg int j=0;j<n;j+=i<<1){

			int w=1;

			for(rg int k=0;k<i;k++){

				int x=a[j+k],y=mul(w,a[j+k+i]);

				a[j+k]=add(x,y),a[j+k+i]=del(x,y),w=mul(w,wn);

			}

		}

	}

	if(f)return ;int inv=mi(n,mod-2);

	for(rg int i=0;i<n;i++)a[i]=mul(a[i],inv);

}

void get_inv(int *a,int *b,int n){

	if(n==1)return b[0]=mi(a[0],mod-2),void();

	get_inv(a,b,(n+1)>>1);int m,len=0;

	for(m=1;m<=n<<1;m<<=1)len++;

	for(rg int i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));

	for(rg int i=0;i<n;i++)c[i]=a[i];

	for(rg int i=n;i<m;i++)c[i]=0;

	ntt(c,m,1),ntt(b,m,1);

	for(rg int i=0;i<m;i++)b[i]=del(mul(2,b[i]),mul(c[i],mul(b[i],b[i])));

	ntt(b,m,0);

	for(rg int i=n;i<m;i++)b[i]=0;

}

void get_ln(int *a,int *b,int n){

	for(rg int i=0;i<n;i++)w[i]=mul(a[i+1],i+1);

	get_inv(a,s,n);int m,len=0;

	for(m=1;m<=n<<1;m<<=1)len++;

	for(rg int i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));

	ntt(w,m,1),ntt(s,m,1);

	for(rg int i=0;i<m;i++)s[i]=mul(s[i],w[i]);

	ntt(s,m,0);b[0]=0;

	for(rg int i=0;i<m;i++)b[i+1]=mul(s[i],mi(i+1,mod-2)),s[i]=w[i]=0;

	for(rg int i=n;i<m;i++)b[i]=0;

}

void get_exp(int *a,int *b,int n){

	if(n==1)return b[0]=1,void();

	get_exp(a,b,(n+1)>>1);get_ln(b,h,n);

	for(rg int i=0;i<n;i++)h[i]=del(a[i],h[i]);h[0]=add(h[0],1);

	int m,len=0;for(m=1;m<=n<<1;m<<=1)len++;

	for(rg int i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));

	ntt(b,m,1),ntt(h,m,1);

	for(rg int i=0;i<m;i++)b[i]=mul(b[i],h[i]);

	ntt(b,m,0);

	for(rg int i=n;i<m;i++)b[i]=0;

}

int main()

{

	read(n),read(k);

	for(rg int i=1,x;i<=n;i++)read(x),v[x]++;

	for(rg int i=1;i<=k;i++)inv[i]=mi(i,mod-2);

	for(rg int i=1;i<=k;i++)

		if(v[i])for(rg int j=i;j<=k;j+=i)a[j]=add(a[j],mul(v[i],inv[j/i]));

	k++;get_exp(a,f,k);

	for(rg int i=1;i<k;i++)printf("%d\n",f[i]);

}

巴特西

luoguP4389 付公主的背包

luogu

最新文章

热门文章