Liveddd's Blog

愛にできることはまだあるかい

P4389 付公主的背包

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 9 分钟

生成函数+多项式，一个经典技巧。

背包问题，考虑使用多项式解决，，容易发现我们要求：

乘法操作并不好实现，我们考虑用 $\ln$ 运算转化为加法，我们有下面的式子：

这个式子可以通过泰勒展开得到，当然也可以通过对两边求导得到。

于是我们要求的式子变成了：

于是直接暴力求出右边的式子，时间复杂度为调和级数 $\mathcal O(n\ln n)$，再做一次 $\exp$，时间复杂度 $\mathcal O(n\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int  N=4e6+10,mod=998244353,G=3,Gi=(mod+1)/G;
template <class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int a[N],b[N],c[N],d[N],e[N],f[N];
int bit,tot,rev[N];

inline int adj(int x){return (x>=mod)?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
	int res=1;
	while(k)
	{
		if(k&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		k>>=1;
	}
	return res;
}
inline void init(int len)
{
	bit=0;
	while((1<<bit)<len)bit++;
	tot=1<<bit;
	for(int i=0;i<tot;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
}
inline void NTT(int *a,int inv)
{
	for(int i=0;i<tot;i++)if(rev[i]<i)swap(a[rev[i]],a[i]);
	for(int mid=1;mid<tot;mid<<=1)
	{
		int g=qpow(inv==1?G:Gi,(mod-1)/(mid<<1));
		for(int i=0;i<tot;i+=(mid<<1))
			for(int j=0,cur=1;j<mid;j++,cur=1ll*cur*g%mod)
			{
				int x=a[i+j],y=1ll*cur*a[i+j+mid]%mod;
				a[i+j]=adj(x+y),a[i+j+mid]=adj(x-y+mod);
			}
	}
	if(inv==-1)
	{
		int inv=qpow(tot,mod-2);
		for(int i=0;i<tot;i++)a[i]=adj(1ll*a[i]*inv%mod+mod);
	}
}
void poly_inv(int *a,int *b,int len)
{
	if(len==1)return b[0]=qpow(a[0]),void();
	poly_inv(a,b,(len+1)>>1);
	init(len<<1);
	for(int i=0;i<tot;i++)c[i]=(i<len?a[i]:0);
	
	NTT(b,1),NTT(c,1);
	for(int i=0;i<tot;i++)b[i]=1ll*adj(2-1ll*b[i]*c[i]%mod+mod)*b[i]%mod;
	NTT(b,-1);
	
	for(int i=len;i<tot;i++)b[i]=0;
}
inline void derivative(int *a,int *b,int len)
{
	for(int i=1;i<len;i++)b[i-1]=1ll*i*a[i]%mod;
	b[len-1]=0;
}
inline void integrate(int *a,int *b,int len)
{
	for(int i=len-1;i;i--)b[i]=1ll*qpow(i)*a[i-1]%mod;
	b[0]=0;
}
inline void poly_ln(int *a,int *b,int len)
{
    poly_inv(a,b,len);
    derivative(a,d,len);
    init(len<<1);
    NTT(b,1),NTT(d,1);
    for(int i=0;i<tot;i++)b[i]=1ll*b[i]*d[i]%mod;
    NTT(b,-1);
    integrate(b,b,len<<1);
}
inline void poly_exp(int *a,int *b,int len)
{
	if(len==1)return b[0]=(a[0]==0),void();
	poly_exp(a,b,(len+1)>>1);
	for(int i=0;i<(len<<1);i++)e[i]=0;
	poly_ln(b,e,len);
	init(len<<1);
	for(int i=0;i<tot;i++)f[i]=(i<len?a[i]:0);
	f[0]++;
	for(int i=0;i<len;i++)f[i]=adj(f[i]-e[i]+mod);
	NTT(b,1),NTT(f,1);
	for(int i=0;i<tot;i++)b[i]=1ll*b[i]*f[i]%mod;
	NTT(b,-1);
	for(int i=len;i<tot;i++)b[i]=0;
}
int m;
int cnt[N];
int inv[N];
int main()
{
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        int x;
        read(x);
        cnt[x]++;
    }
    for(int i=1;i<=m;i++)inv[i]=qpow(i);
    for(int i=1;i<=m;i++)
    {
        if(!cnt[i])continue;
        for(int j=1;i*j<=m;j++)
            a[i*j]=adj(a[i*j]+1ll*cnt[i]*inv[j]%mod);
    }
    poly_exp(a,b,m+1);
    for(int i=1;i<=m;i++)printf("%d\n",b[i]);
    return 0;
}