注意
初始化的时候要这样写
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
v[x]++;
}
for(int i=1;i<=m;i++){
if(v[i]){
for(int j=1;j<=m/i;j++)
a[i*j]=(a[i*j]+1LL*v[i]*invx[j]%MOD)%MOD;
}
}
这样写的复杂度是调和级数（\(O(n\log n)\)）
不能这样写
for(int i=1;i<=n;i++){
scanf("%d",&v[i]);
for(int j=0;v[i]*j-1<=m;j++)
if(v[i]*j-1>=0)
a[v[i]*j-1]+=v[i];
}
因为权值可能重复，这样的话复杂度就不对了
思路
题目要求的答案是
\[\prod_{k=1}^n \sum_{i=1}^\infty x^{iV_k}
\]
\]
直接卷积的复杂度是\(O(nm\log m)\)，考虑一个化乘法为加法的思路：把所有多项式取\(\ln\)之后加起来求\(\exp\)
设
\[A_k(x)=\sum_{i=1}^\infty x^{iV_k}=\frac{1}{1-x^{V_k}}
\]
\]
即
\[\prod_{k=1}^n e^{\ln(A(x))}= e^{\sum_{k=1}^n \ln(A(x))}
\]
\]
所以问题转化成了如何快速求\(\sum_{k=1}^n \ln(A(x))\)
\[\begin{align} &\sum_{k=1}^n \ln(A(x))\\=& \sum_{k=1}^n \int \frac{A'(x)}{A(x)}\\=&\int \sum_{k=1}^n \frac{(\sum_{i=1}^\infty x^{iV_k})'}{\frac{1}{1-x^{V_k}}}\\=&\int \sum_{k=1}^n (1-x^{V_k})\sum_{i=1}^\infty iV_kx^{iV_k-1}\\=&\int \sum_{k=1}^n V_k\sum_{i=1}^{\infty} x^{iV_k-1}\\=&\sum_{k=1}^n\sum_{i=1}^{\infty}\frac{V_{k}}{iV_k}x^{iV_k}\\=&\sum_{k=1}^n\sum_{i=1}^{\infty}\frac{1}{i}x^{iV_k}\end{align}
\]
\]
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 300000;
const int G = 3;
const int invG = 332748118;
const int MOD = 998244353;
int rev[MAXN],invx[MAXN];
int pow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=(1LL*ans*a)%MOD;
a=(1LL*a*a)%MOD;
b>>=1;
}
return ans;
}
void cal_rev(int *rev,int n,int lim){
for(int i=0;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));
}
void NTT(int *a,int opt,int n,int lim){
for(int i=0;i<n;++i)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(int i=2;i<=n;i<<=1){
int len=i/2;
int tmp=pow((opt)?G:invG,(MOD-1)/i);
for(int j=0;j<n;j+=i){
int arr=1;
for(int k=j;k<j+len;k++){
int t=(1LL*a[k+len]*arr)%MOD;
a[k+len]=(a[k]-t+MOD)%MOD;
a[k]=(a[k]+t)%MOD;
arr=(1LL*arr*tmp)%MOD;
}
}
}
if(!opt){
int invN=pow(n,MOD-2);
for(int i=0;i<n;++i)
a[i]=(1LL*a[i]*invN)%MOD;
}
}
void mul(int *a,int *b,int &at,int bt){
static int tmp1[MAXN];
int num=(at+bt),n=1,lim=0;
while(n<=(num+2))
n<<=1,lim++;
for(int i=0;i<n;++i)
tmp1[i]=b[i];
cal_rev(rev,n,lim);
NTT(a,1,n,lim);
NTT(tmp1,1,n,lim);
for(int i=0;i<n;++i)
a[i]=(1LL*a[i]*tmp1[i])%MOD;
NTT(a,0,n,lim);
at=num;
}
void inv(int *a,int *b,int dep,int &midlen,int &midlim){
if(dep==1){
b[0]=pow(a[0],MOD-2);
return;
}
inv(a,b,(dep+1)>>1,midlen,midlim);
static int tmp[MAXN];
while((dep<<1)>midlen)
midlen<<=1,midlim++;
for(int i=0;i<dep;++i)
tmp[i]=a[i];
for(int i=dep;i<midlen;++i)
tmp[i]=0;
cal_rev(rev,midlen,midlim);
NTT(tmp,1,midlen,midlim);
NTT(b,1,midlen,midlim);
for(int i=0;i<midlen;++i)
b[i]=1LL*b[i]*(2-1LL*tmp[i]*b[i]%MOD+MOD)%MOD;
NTT(b,0,midlen,midlim);
for(int i=dep;i<midlen;++i)
b[i]=0;
}
void qd(int *a,int &at){
for(int i=0;i<at;++i)
a[i]=(1LL*a[i+1]*(i+1))%MOD;
a[at]=0;
at--;
}
void jf(int *a,int &at){
at++;
for(int i=at;i>=1;i--)
a[i]=(1LL*a[i-1]*invx[i])%MOD;
a[0]=0;
}
void ln(int *a,int *b,int &at){
static int tmp[MAXN];
int midlen=1,midlim=0,tmpt=at,bt=at;
for(int i=0;i<=at;++i)
tmp[i]=a[i];
inv(a,b,at+1,midlen,midlim);
qd(tmp,tmpt);
mul(b,tmp,at,tmpt);
jf(b,tmpt);
for(int i=bt+1;i<=at;++i)
b[i]=0;
at=bt;
}
void exp(int *a,int *b,int dep){
if(dep==1){
b[0]=1;
return;
}
exp(a,b,(dep+1)>>1);
static int tmp1[MAXN];
for(int i=0;i<dep;++i)
tmp1[i]=0;
ln(b,tmp1,dep);
for(int i=0;i<dep;++i)
tmp1[i]=(a[i]-tmp1[i]+MOD)%MOD;
tmp1[0]+=1;
int midlen=dep-1;
mul(b,tmp1,midlen,dep-1);
for(int i=dep;i<midlen;++i)
b[i]=0;
}
void inv_init(int n){
invx[0]=0;
invx[1]=1;
for(int i=2;i<=n;i++)
invx[i]=1LL*(MOD-MOD/i)*invx[MOD%i]%MOD;
}
int a[MAXN],b[MAXN],n,m,v[MAXN];
int main(){
scanf("%d %d",&n,&m);
inv_init(m+1);
// for(int i=1;i<=n;i++){
// scanf("%d",&v[i]);
// for(int j=0;v[i]*j-1<=m;j++)
// if(v[i]*j-1>=0)
// a[v[i]*j-1]+=v[i];
// }
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
v[x]++;
}
for(int i=1;i<=m;i++){
if(v[i]){
for(int j=1;j<=m/i;j++)
a[i*j]=(a[i*j]+1LL*v[i]*invx[j]%MOD)%MOD;
}
}
// jf(a,m);
exp(a,b,m+1);
for(int i=1;i<=m;i++)
printf("%d\n",b[i]);
return 0;
}