[luogu 4389] 付公主的背包

题意：求一个较大的多重背包对于每个i的方案数，答案对998244353取模。

思路：

生成函数：

对于一个\(V\)

设：

\(f(x) = \sum_{i=0}^{oo} x ^ {V * i} = {1 \over {1 - x ^ V}}\)

那么就是求这个生成函数的积。

首先将\(f(x)\)取\(ln\)为\(g(x)\)，最后\(exp\)回去得到答案。

\(g'(x) = {f'(x) \over f(x)} = (1 - x^V)\sum_{i = 1}^{oo}V * i * x ^ {V}\)

最终\(exp\)一遍得到答案。

时间复杂度\(O(mlogm)\)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5000010;

const int mod = 998244353;

const int g = 3;

#define ll long long

int A[maxn];

int B[maxn];

int c[maxn],d[maxn];

int e[maxn];

int f[maxn];

int w[maxn][2];

int rev[maxn];

int cnt[maxn];

int v[maxn];

int ans[maxn];

int inv[maxn];

const int vg = (mod + 1) / 3;

int n,m,l;

int len;

inline int read() {

	int q=0,f=1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;ch=getchar();

	}

	while(isdigit(ch)){

		q=q*10+ch-'0';ch=getchar();

	}

	return q*f;

}

inline int pow_mod (int x,int y) {

	int res = 1;

	while(y) {

		if(y & 1) res = (ll) res * x % mod;

		x = (ll) x * x % mod;

		y >>= 1;

	}

	return res;

}

inline void NTT(int *a,int n,int type) {

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

	for(int i = 0;i < len; ++i) {

		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	}

	for(int i = 0;i < len; ++i) {

		if(i < rev[i]) {

			swap(a[i],a[rev[i]]);

		}

	}

	for(int i = 1;i < len; i <<= 1) {

		int wn = (~type) ? w[i][0]:w[i][1];

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

			int w = 1;

			for(int k = 0;k < i; ++k,w = (ll)w * wn % mod) {

				int x = (ll)a[i + j + k];

				int y = a[j + k];

				a[j + k] = (x + y) % mod;

				a[i + j + k] = (y + mod - x) % mod;

			}

		}

	}

	if(type == -1) {

		int tmp = pow_mod(len,mod - 2);

		for(int i = 0;i < len; ++i) {

			a[i] = (ll)a[i] * tmp % mod;

		}

	}

}

inline void get_Inv(int *a,int *b,int n) {

	if(n == 1) {

		b[0] = pow_mod(a[0],mod - 2);

		return;

	}

	get_Inv(a,b,n >> 1);

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

		A[i] = a[i];

		B[i] = b[i];

	}

	NTT(A,n << 1,1);

	NTT(B,n << 1,1);

	for(int i = 0;i < len; ++i) {

		A[i] = (ll)A[i] * B[i] % mod * B[i] % mod;

	}

	NTT(A,n << 1,-1);

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

		b[i] = ((b[i] << 1) % mod - A[i] + mod) % mod;

	}

	for(int i = 0;i < len; ++i) {

		A[i] = B[i] = 0;

	}

}

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

	get_Inv(a,c,n);

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

		d[i] = (ll)(i + 1) * a[i + 1] % mod;

	}

	NTT(c,n << 1,1);

	NTT(d,n << 1,1);

	for(int i = 0;i < len; ++i) {

		c[i] = (ll) c[i] * d[i] % mod;

	}

	NTT(c,n << 1,-1);

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

		b[i] = (ll)inv[i] * c[i - 1] % mod;

	}

	for(int i = 0;i < len; ++i) {

		c[i] = d[i] = 0;

	}

}

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

	if(n == 1) {

		b[0] = 1;

		return;

	}

	get_exp(a,b,n >> 1);

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

		e[i] = b[i];

	}

	get_ln(b,f,n);

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

		f[i] = (mod - f[i] + a[i]) % mod;

		f[0] = (f[0] + 1)%mod;

	}

	NTT(e,n << 1,1);

	NTT(f,n << 1,1);

	for(int i = 0;i < len; ++i) {

		e[i] = (ll)e[i] * f[i] % mod;

	}

	NTT(e,n << 1,-1);

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

		b[i] = e[i];

	}

	for(int i = 0;i < len; ++i) {

		e[i] = f[i] = 0;

	}

}

int main () {

	n = read(),m = read();

	inv[1] = 1;

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

		++cnt[read()];

	}

	int tmp = 1;

	for(;tmp <= m;tmp <<= 1);

	for(int i = 1;i <= (tmp << 1);i <<= 1) {

		w[i][0] = pow_mod(g,(mod - 1)/(i << 1));

		w[i][1] = pow_mod(vg,(mod - 1)/(i<<1));

	}

	for(int i = 2;i <= tmp; ++i) {

		inv[i] = (ll)(mod - mod / i) * inv[mod % i]%mod;

	}

	for(int i = 1;i <= m; ++i) {

		if(cnt[i]) {

			int dl = (ll) i * cnt[i] % mod;

			for(int j = 1;i * j <= m; ++j) {

				v[i * j] = (v[i * j] + dl) % mod;

			}

		}

	}

	for(int i = 1;i <= m; ++i) {

		v[i] = (ll)inv[i] * v[i] % mod;

	}

	get_exp(v,ans,tmp);

	for(int i = 1;i <= m; ++i) {

		printf("%d\n",ans[i] % mod);

	}

	return 0;

}

//原地爆炸

巴特西

[luogu 4389] 付公主的背包

最新文章

热门文章