欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷·付公主的背包

程序员文章站 2022-03-13 16:59:36
...

初见安~这里是传送门:洛谷P4389 付公主的背包

洛谷·付公主的背包

题解

30%的数据明显我们可以暴力跑背包,但是大点点就不行了。我们考虑多项式。

根据母函数,我们对于每一种物品都可以写成一个多项式的形式,比如某物品大小为v,那么就有多项式:

洛谷·付公主的背包

对于n个物品,我们将他们每个的多项式都乘起来,所求就是最后那个多项式的前n项的系数。

但是这样做的复杂度是多少?洛谷·付公主的背包,明显过不了。所以我们可能还要优化一下公式。

对于第i个物品的多项式为:

洛谷·付公主的背包【无穷等比数列求和

所以我们要求的就是:

洛谷·付公主的背包

全是累乘啊。我们把乘法变加法,两边同时取对。

洛谷·付公主的背包

现在看起来已经差不多了,那么我们的问题就是f(i)了。因为我们的物品并不是真的可以取用无限个的,所以这个式子我们还得继续展开,在合适的时候回到这个限制上。

因为有:洛谷·付公主的背包

所以我们把f(i)带进去:【这里是求洛谷·付公主的背包,直接用洛谷·付公主的背包代替洛谷·付公主的背包了。这一步求导+积分可以手推一下,下面是个平方项的,后来约掉了

洛谷·付公主的背包

里面好像有个洛谷·付公主的背包,所以我们是时候展开了:【最后这一步积分的还原式手推也会有点点吃力QuQ套求导公式吧。加油

洛谷·付公主的背包

至此,就是洛谷·付公主的背包了。因为回到上面,我们括号里面是洛谷·付公主的背包求和,所以n个多项式对应的系数相加即可,最后exp回来就是所求了。

感觉这个题就是在考你数学的导数变换啊……恐怖。

上代码——

#include<algorithm>//princes Fu
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 300005
using namespace std;
typedef long long ll;
const int mod = 998244353;
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

int len, l, r[maxn];
ll pw(ll a, ll b) {ll res = 1; while(b) {if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
void NTT(ll *c, int flag) {
	for(int i = 1; i <= len; i++) if(i < r[i]) swap(c[i], c[r[i]]);
	for(int mid = 1; mid < len; mid <<= 1) {
		ll gn = pw(3, (mod - 1) / (mid << 1));
		if(flag == -1) gn = pw(gn, mod - 2);
		for(int ls = 0, L = mid << 1; ls < len; ls += L) {
			ll g = 1;
			for(int k = 0; k < mid; k++, g = g * gn % mod) {
				ll x = c[ls + k], y = c[ls + mid + k] * g % mod;
				c[ls + k] = (x + y) % mod, c[ls + mid + k] = (x - y + mod) % mod;
			}
		}
	}
	if(flag == 1) return;
	ll rev = pw(len, mod - 2);
	for(int i = 0; i <= len; i++) c[i] = c[i] * rev % mod;
}

ll tmp[maxn];
void get_inv(ll *a, ll *b, int n) {
	if(n == 1) {b[0] = pw(a[0], mod - 2); return;};
	get_inv(a, b, n + 1 >> 1);
	len = 1, l = 0;
	while(len <= n + n) len <<= 1, l++;
	for(int i = 1; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
	
	for(int i = 0; i < n; i++) tmp[i] = a[i];
	for(int i = n; i <= len; i++) tmp[i] = 0;
	NTT(tmp, 1), NTT(b, 1);
	for(int i = 0; i <= len; i++) b[i] = b[i] * (1ll * 2 - b[i] * tmp[i] % mod + mod) % mod;
	NTT(b, -1); for(int i = n; i <= len; i++) b[i] = 0;
}

void deriv(ll *a, int n) {for(int i = 1; i < n; i++) a[i - 1] = a[i] * i % mod; a[n - 1] = 0;}
void integ(ll *a, int n) {for(int i = n - 1; i > 0; i--) a[i] = a[i - 1] * pw(i, mod - 2) % mod; a[0] = 0;}
void get_ln(ll *a, ll *b, int n) {
	get_inv(a, b, n);
	for(int i = 0; i < n; i++) tmp[i] = a[i];
	for(int i = n; i <= len; i++) tmp[i] = 0;
	deriv(tmp, n);
	NTT(tmp, 1), NTT(b, 1);
	for(int i = 0; i <= len; i++) b[i] = b[i] * tmp[i] % mod;
	NTT(b, -1); integ(b, n);
}

ll c[maxn];
void get_exp(ll *a, ll *b, int n) {
	if(n == 1) {b[0] = 1; return;}
	get_exp(a, b, n + 1 >> 1);
	memset(c, 0, sizeof c);
	get_ln(b, c, n);
	c[0] = (1 - c[0] + a[0] + mod) % mod;
	for(int i = 1; i < n; i++) c[i] = (a[i] - c[i] + mod) % mod;
	
	NTT(c, 1), NTT(b, 1);
	for(int i = 0; i <= len; i++) b[i] = b[i] * c[i] % mod;
	NTT(b, -1);
	for(int i = n; i <= len; i++) b[i] = 0;
}//从这里往上都是为了求exp的模板操作,可以不看

int n, m, cnt[maxn];
ll f[maxn], g[maxn];
signed main() {
	n = read(), m = read();
	for(int i = 1, x; i <= n; i++) x = read(), cnt[x]++;//cnt计数,有些物品就可以一起处理了
	for(int v = 1; v <= m; v++) if(cnt[v]) { 
		for(int i = v; i <= m; i += v) f[i] = (f[i] + cnt[v] * pw(i / v, mod - 2));
	}//开个桶累加最后推出来的那个公式的内容
	get_exp(f, g, m + 1);//exp过去
	for(int i = 1; i <= m; i++) printf("%lld\n", g[i]);//就没了……
	return 0;
}

迎评:)
——End——

相关标签: 数论