付公主的背包
wangyuchen
2018-08-14 10:58:47
## 解法
答案显然是$n$个形如$\sum_{i \geq 1} x^{vi}$的多项式的卷积
然而直接NTT的时间复杂度是$O(nm\log n)$
我们可以把每个多项式$k$求$\ln$然后相加， 在$\exp$回去
我们设$f(x) = \sum_{i \geq 1} x^{vi}$， $g(x) = \ln(f(x))$
我们知道$f(x) = \frac{1}{1-x^v}$
于是
$$g'(x) = \frac{f'(x)}{f(x)} = \frac{f'(x))}{\frac{1}{1-x^v}} = (1-x^v)f'(x) = (1-x^v)\sum_{i \geq 1} v\times i\times x^{vi-1} = \sum_{i \geq 1} v\times [i - (i-1)]\times x^{vi-1} = \sum_{i \geq 1} v\times x^{vi-1}$$
$$g(x) = \sum_{i \geq 1} \frac{1}{i}x^{vi}$$
再跑多项式$\exp$就行了
## 代码
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 400010;
const LL mod = 998244353LL;
inline LL power(LL a, LL n, LL mod)
{ LL Ans = 1;
while (n)
{ if (n & 1) Ans = (Ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return Ans;
}
inline LL Plus(LL a, LL b) { return a + b > mod ? a + b - mod : a + b; }
inline LL Minus(LL a, LL b) { return a - b < 0 ? a - b + mod : a - b; }
struct Mul
{ int Len;
int rev[N];
LL wn[N];
void getReverse()
{ for (int i = 0; i < Len; i++)
rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len >> 1));
}
void NTT(LL * a, int opt)
{ getReverse();
for (int i = 0; i < Len; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
int cnt = 0;
for (int i = 2; i <= Len; i <<= 1)
{ cnt++;
for (int j = 0; j < Len; j += i)
{ LL w = 1;
for (int k = 0; k < (i>>1); k++)
{ LL x = a[j + k];
LL y = (w * a[j + k + (i>>1)]) % mod;
a[j + k] = Plus(x, y);
a[j + k + (i>>1)] = Minus(x, y);
w = (w * wn[cnt]) % mod;
}
}
}
if (opt == -1)
{ reverse(a + 1, a + Len);
LL num = power(Len, mod-2, mod);
for (int i = 0; i < Len; i++)
a[i] = (a[i] * num) % mod;
}
}
void init()
{ for (int i = 0; i < 23; i++)
wn[i] = power(3LL, (mod-1) / (1 << i), mod);
}
void getLen(int l)
{ Len = 1;
for (; Len <= l; Len <<= 1);
}
} Calc;
void cpy(LL * A, LL * B, int len1, int len2)
{ for (int i = 0; i < len1; i++) A[i] = B[i];
for (int i = len1; i < len2; i++) A[i] = 0;
}
void getInv(LL * A, LL * B, int len)
{ static LL tmp1[N], tmp2[N];
B[0] = power(A[0], mod-2, mod);
for (register int i = 2; i <= len; i <<= 1)
{ Calc.Len = i << 1;
cpy(tmp1, A, i, Calc.Len);
cpy(tmp2, B, i >> 1, Calc.Len);
Calc.NTT(tmp1, 1);
Calc.NTT(tmp2, 1);
for (register int j = 0; j < Calc.Len; j++)
tmp1[j] = Minus(Plus(tmp2[j], tmp2[j]), tmp2[j] * tmp2[j] % mod * tmp1[j] % mod);
Calc.NTT(tmp1, -1);
for (register int j = 0; j < i; j++)
B[j] = tmp1[j];
}
}
void getDeri(LL * a, int len)
{ for (int i = 0; i < len; i++)
a[i] = a[i+1] * (LL) (i+1) % mod;
}
void getInte(LL * a, int len)
{ for (int i = len-1; i >= 1; i--)
a[i] = a[i-1] * power(i, mod-2, mod) % mod;
a[0] = 0;
}
void getLn(LL * A, int len)
{ static LL tmp1[N], tmp2[N], tmp3[N];
Calc.Len = len << 1;
cpy(tmp1, A, len, Calc.Len);
cpy(tmp2, A, len, Calc.Len);
getDeri(tmp1, len);
getInv(tmp2, tmp3, len);
Calc.Len = len << 1;
Calc.NTT(tmp1, 1);
Calc.NTT(tmp3, 1);
for (int i = 0; i < Calc.Len; i++)
tmp1[i] = tmp1[i] * tmp3[i] % mod;
Calc.NTT(tmp1, -1);
for (int i = len; i < Calc.Len; i++)
tmp1[i] = 0;
getInte(tmp1, len);
for (int i = 0; i < len; i++)
A[i] = tmp1[i];
}
void getExp(LL * A, LL * B, int len)
{ static LL tmp1[N], tmp2[N];
B[0] = 1;
for (int i = 2; i <= len; i <<= 1)
{ Calc.Len = i << 1;
cpy(tmp1, B, Calc.Len, Calc.Len);
cpy(tmp2, B, Calc.Len, Calc.Len);
getLn(tmp1, i);
Calc.Len = i << 1;
for (int j = 0; j < i; j++)
tmp1[j] = Minus(A[j], tmp1[j]);
tmp1[0]++;
Calc.NTT(tmp1, 1);
Calc.NTT(tmp2, 1);
for (int j = 0; j < Calc.Len; j++)
tmp1[j] = (tmp1[j] * tmp2[j]) % mod;
Calc.NTT(tmp1, -1);
for (int j = 0; j < Calc.Len; j++)
B[j] = tmp1[j];
}
}
LL A[N], B[N], Ans[N];
int cnt[N];
int v[N];
int main()
{ int n, m;
scanf("%d %d", &n, &m);
Calc.init();
for (int i = 1; i <= n; i++)
{ scanf("%d", &v[i]);
cnt[v[i]]++;
}
Calc.init();
Calc.getLen(m);
int len = Calc.Len;
for (int i = 1; i <= m; i++)
{ if (!cnt[i]) continue;
for (int j = i; j <= m; j += i)
A[j] = Plus(A[j], (LL) cnt[i] * i % mod * power(j, mod-2, mod) % mod);
}
getExp(A, Ans, len);
for (int i = 1; i <= m; i++)
printf("%lld\n", Ans[i]);
return 0;
}
```