自动搬运

查看原文

来自洛谷，原作者为

	yybyyb **

搬运于2025-08-24 21:59:39，当前版本为作者最后更新于2018-03-31 20:03:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题太神了，无限$orz$出题人

$30$分的部分分很显然就是一个背包。并没有什么好说的。

纯随机的数据并不知道怎么乱搞。

所以我直接写我的方法了。。。。

既然背包做不了，又是求一类计数问题的答案，再加上我最近正好再做生成函数这一套理论。这道题目就往这方面想了。

我们假设物品的数量比较少，来看看怎么做这道题目。首先每个物品的个数可以直接看成无限，那么对于一个体积为$V$的物品，我们可以直接构建生成函数。

$$A(x)=\sum_{i=0}^{\infty}[i\%V=0]x^i=\frac{1}{1-x^V} $$

显然答案就是$m$个生成函数的卷积。

如果直接做答案是$O(mn\log n)$，显然不是正确的复杂度。

我们看看怎么优化。

生成函数除了形式幂级数的形式还有封闭形式，我在$A(x)$的后面已经写出了封闭形式，所以只需要把封闭形式的卷积求出来，然后求个逆还原多项式就行了。

但是这样的复杂度是$O(2^m)$，还是$GG$

我们要考虑一个方法，能够把乘法化简。很自然的想到同时取对数之后就变成了加法，但是多项式求$\ln$的复杂度也是$O(n\log n)$的，但是我们的多项式很特殊，具体的，我们有

$$\ln(1-x^V)=-\sum_{i\ge 1}\frac{x^{Vi}}{i}$$

推导如下：

$$\begin{aligned}\ln F(x)=G(x)\\\frac{F'(x)}{F(x)}=G'(x)\\\frac{-Vx^{V-1}}{1-x^V}=G'(x)\\-\sum_{i\ge 0}Vx^{V-1+Vi}=G'(x)\\-\sum_{i \ge 0}\frac{Vx^{V+Vi}}{V+Vi}=G(x)\\-\sum_{i \ge 1}\frac{x^{Vi}}{i}=G(x)\end{aligned} $$

于是，统计每一个容量的物品个数，然后$O(m/V)$给对应的位置加上系数，这样总的复杂度是$O(n\log n)$的。

做完这一步相当于给每个封闭形式求$\ln$之后求完了和。

直接多项式$\exp$再多项式求逆之后还原多项式，输出答案即可。

提供我的大常数代码。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 277777
const int MOD=998244353;
const int Phi=MOD-1;
const int gr=3;
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int fpow(int a,int b)
{
    int s=1;
    while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
    return s;
}
int r[MAX],N,l,M;
int Og[MAX];
void NTT(int *P,int opt,int n)
{
    for(N=1,l=0;N<n;N<<=1)++l;
    for(RG int i=0;i<N;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    for(RG int i=0;i<N;++i)if(i<r[i])swap(P[i],P[r[i]]);
    for(RG int i=1;i<N;i<<=1)
    {
        RG int W=fpow(gr,Phi/(i<<1));Og[0]=1;
        for(RG int j=1;j<i;++j)Og[j]=1ll*Og[j-1]*W%MOD;
        for(RG int p=i<<1,j=0;j<N;j+=p)
            for(RG int k=0;k<i;++k)
            {
                RG int X=P[j+k],Y=1ll*Og[k]*P[i+j+k]%MOD;
                P[j+k]=(X+Y)%MOD;P[i+j+k]=(X+MOD-Y)%MOD;
            }
    }
    if(opt==-1)
    {
        reverse(&P[1],&P[N]);
        for(RG int i=0,inv=fpow(N,MOD-2);i<N;++i)P[i]=1ll*P[i]*inv%MOD;
    }
}
int inv[MAX];
void initinv(int N)
{
    inv[0]=inv[1]=1;
    for(RG int i=2;i<N;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
int A[MAX],B[MAX];
void Inv(int *a,int *b,int len)
{
    if(len==1){b[0]=fpow(a[0],MOD-2);return;}
    Inv(a,b,len>>1);
    for(RG int i=0;i<len;++i)A[i]=a[i],B[i]=b[i];
    NTT(A,1,len<<1);NTT(B,1,len<<1);
    for(RG int i=0;i<(len<<1);++i)A[i]=1ll*A[i]*B[i]%MOD*B[i]%MOD;
    NTT(A,-1,len<<1);
    for(RG int i=0;i<len;++i)b[i]=(b[i]+b[i])%MOD;
    for(RG int i=0;i<len;++i)b[i]=(b[i]+MOD-A[i])%MOD;
    for(RG int i=0;i<(len<<1);++i)A[i]=B[i]=0;
}
int C[MAX],D[MAX];
void Dao(int *a,int *b,int len)
{
    for(RG int i=1;i<len;++i)b[i-1]=1ll*i*a[i]%MOD;
    b[len]=b[len-1]=0;
}
void Jifen(int *a,int *b,int len)
{
    for(RG int i=1;i<len;++i)b[i]=1ll*a[i-1]*inv[i]%MOD;
    b[0]=0;
}
void Getln(int *a,int *b,int len)
{
    int A[MAX],B[MAX];
    memset(A,0,sizeof(A));memset(B,0,sizeof(B));
    Dao(a,A,len);
    Inv(a,B,len);
    NTT(A,1,len<<1);NTT(B,1,len<<1);
    for(RG int i=0;i<(len<<1);++i)A[i]=1ll*A[i]*B[i]%MOD;
    NTT(A,-1,len<<1);
    Jifen(A,b,len);
    for(RG int i=0;i<(len<<1);++i)A[i]=B[i]=0;
}
int E[MAX];
void Exp(int *a,int *b,int len)
{
    if(len==1){b[0]=1;return;}
    Exp(a,b,len>>1);
    for(RG int i=0;i<len;++i)D[i]=b[i];
    Getln(b,E,len);
    for(RG int i=0;i<len;++i)E[i]=(MOD-E[i]+a[i])%MOD;E[0]=(E[0]+1)%MOD;
    NTT(E,1,len<<1);NTT(D,1,len<<1);
    for(RG int i=0;i<(len<<1);++i)D[i]=1ll*D[i]*E[i]%MOD;
    NTT(D,-1,len<<1);
    for(RG int i=0;i<len;++i)b[i]=D[i];
    for(RG int i=0;i<(len<<1);++i)D[i]=E[i]=0;
}
void FastPow(int *a,int *b,int K,int len)
{
    int E[MAX];memset(E,0,sizeof(E));
    Getln(a,E,len);
    for(RG int i=0;i<len;++i)E[i]=1ll*K*E[i]%MOD;
    Exp(E,b,len);
}
int X[MAX],Y[MAX];
int n,K,TT[MAX],m;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)TT[read()]++;
    int N;for(N=1;N<=m;N<<=1);initinv(N);
    for(int i=1;i<=m;++i)
        if(TT[i])
            for(int j=i;j<N;j+=i)
                X[j]=(X[j]+1ll*TT[i]*(MOD-inv[j/i]))%MOD;
    Exp(X,Y,N);memset(X,0,sizeof(X));Inv(Y,X,N);
    for(int i=1;i<=m;++i)printf("%d\n",X[i]);
    return 0;
}