前置芝士：[NTT与多项式全家桶](https://www.luogu.org/blog/command-block/ntt-yu-duo-xiang-shi-quan-jia-tong)+生成函数OGF+(无标号计数)
这道题好像是WC2019讲义上的经典例题?
大家都直接`OGF`然后丢式子,我觉得不太友好,实际上这是一道Euler无标号计数的**模板**题。
先讲一讲这题为啥是无标号计数。
设$C[i]$为大小为$i$的物品个数,相当于我们有$C[i]$种方案得到一个大小为$i$的元素。
随后,我们要选取若干个元素使得他们的大小和为$m$,元素之间无顺序之分。
这不就是背包问题吗?所以背包问题是最经典的无标号计数。
------------
- `EGF`的 $\exp$
大家都知道,如果是有标号计数,选用`EGF`的话:
我们得到了单个元素的`EGF`,只要`EXP`一下就能得到这些元素生成的集合的`EGF`,这个可以泰勒展开然后观察式子。
有$\exp(F(x))=\sum\limits_{i=0}\dfrac{F(x)^i}{i!}$
注意$\dfrac{F(x)^i}{i!}$的意义 : 选择$i$个元素映射到标号上,但他们之间没有关联,顺序不用考虑。
现在是无标号计数,我们自然也想要优美的变换啦。
无标号计数中,如果两个元素大小相同且内部相同,则无法区分。
也就是说,我们考虑单独的$F[i]$,其贡献为 : $(1+x^i+x^{2i}+...)^{F[i]}$
意思就是对大小为$i$的每种方案分别建立`OGF`然后乘起来。
我们就得到了Euler变换:
$$Euler(F(x))=\prod\limits_{i=0}\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}$$
那么问题来了,怎么计算这个东西?
容易想到 $\ln$ 之后变为加法,再 $\exp$ ,则有:
$$\exp\sum\limits_{i=0}\ln\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}$$
- $\ln\Big(\dfrac{1}{1-x^p}\Big)^{c}$
考虑$\ln(x^c)=c·\ln x$,次数$c$我们就暂且按下不表。
先来搞$\frac{1}{1-x}$,这东西的展开是$\{1,1,1,1,1...\}$
众所周知 $\ln A(x)=∫(\frac{A'(x)}{A(x)})$
先对这东西求导,得到$\{1,2,3,4,5...\}=\dfrac{1}{(1-x)^2}$
然后求逆,是$1-x$,乘在一起又回到了$\frac{1}{1-x}$
然后是积分,得到$\{0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}$
也就是$\ln \frac{1}{1-x}=\sum\limits_{i=1}\dfrac{x}{i}$
现在用$x^p$替换$x$得到$\ln \frac{1}{1-x^p}=\sum\limits_{i=1}\dfrac{x^{ip}}{i}$
在$\!\pmod{x^n}$下也就$n/p$个有效项。
给出一个比较方便化简的中间结果 : $Euler(F(x))=\exp\sum\limits_{i=0}-F[i]*\ln(1-x^i)$
对于每个$p$暴力求和复杂度是$O(\sum_{i=1}^n\frac{n}{i})=O(nlogn)$的,随后`EXP`即可。
这题就是直接计算$Euler(C(x))$,非常的模板啊。
**Code:**
```cpp
// luogu-judger-enable-o2
#include<algorithm>
#include<cstdio>
#define mod 998244353
#define G 3
#define Maxn 100500
using namespace std;
inline int read()
{
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
int n,m,r[Maxn<<2],invn,invG;
long long powM(long long a,long long t=mod-2)
{
long long ans=1,buf=a;
while(t){
if(t&1)ans=(ans*buf)%mod;
buf=(buf*buf)%mod;
t>>=1;
}return ans;
}
void NTT(long long *f,int n,short op)
{
for (int i=0;i<n;i++)
if (r[i]<i)swap(f[r[i]],f[i]);
for (int p=2;p<=n;p<<=1){
int len=p>>1,
w=powM(op==1 ?G:invG,(mod-1)/p);
for (int k=0;k<n;k+=p){
long long buf=1;
for (int i=k;i<k+len;i++){
int sav=f[len+i]*buf%mod;
f[len+i]=(f[i]-sav+mod)%mod;
f[i]=(f[i]+sav)%mod;
buf=buf*w%mod;
}
}
}
}
long long _g[Maxn<<2];
void times(long long *f,long long *gg,int len1,int len2,int limit)
{
int n=1;
for(;n<len1+len2;n<<=1);
long long *g=_g;
for (int i=0;i<len2;i++)g[i]=gg[i];
for (int i=len2;i<n;i++)g[i]=0;
invn=powM(n);
for(int i=0;i<n;i++)
r[i]=(r[i>>1]>>1)|((i&1)?n>>1:0);
NTT(f,n,1);NTT(g,n,1);
for(int i=0;i<n;++i)f[i]=(f[i]*g[i])%mod;
NTT(f,n,-1);
for(int i=0;i<limit;++i)f[i]=f[i]*invn%mod;
for(int i=limit;i<n;++i)f[i]=0;
}
long long _r[Maxn<<2],_rr[Maxn<<2];
void invp(long long *f,int plen)
{
long long *r=_r,*rr=_rr;
int n=1;for(;n<plen;n<<=1);
rr[0]=powM(f[0]);
for (int len=2;len<=n;len<<=1){
for (int i=0;i<len;i++)
r[i]=rr[i]*2%mod;
times(rr,rr,len/2,len/2,len);
times(rr,f,len,len,len);
for (int i=0;i<len;i++)
rr[i]=(r[i]-rr[i]+mod)%mod;
}for (int i=0;i<plen;i++)
f[i]=rr[i];
for (int i=0;i<n;i++)rr[i]=r[i]=0;
}
void dao(long long *f,int m)
{
for (int i=1;i<m;i++)
f[i-1]=f[i]*i%mod;
f[m-1]=0;
}
void jifen(long long *f,int m)
{
for (int i=m;i;i--)
f[i]=f[i-1]*powM(i)%mod;
f[0]=0;
}
long long _lns[Maxn<<2];
void lnp(long long *f,int m)
{
long long *sav=_lns;
for (int i=0;i<m;i++)sav[i]=f[i];
invp(sav,m);dao(f,m);
times(f,sav,m-1,m,m);
jifen(f,m-1);
for (int i=0;i<m;i++)sav[i]=0;
}
long long _xp[Maxn<<2],_xp2[Maxn<<2];
void exp(long long *f,int m)
{
long long *s=_xp,*ss=_xp2;
int n=1;for(;n<m;n<<=1);
ss[0]=1;
for (int len=2;len<=n;len<<=1){
for (int i=0;i<len/2;i++)s[i]=ss[i];
for (int i=len/2;i<len;i++)s[i]=0;
lnp(s,len);
for (int i=0;i<len;i++)
s[i]=(f[i]-s[i]+mod)%mod;
s[0]=(s[0]+1)%mod;
times(ss,s,len/2,len,len);
}for (int i=0;i<m;i++)f[i]=ss[i];
for (int i=0;i<n;i++)s[i]=ss[i]=0;
}
long long f[Maxn<<2],inv[Maxn];
int c[Maxn];
int main()
{
invG=powM(G);
scanf("%d%d",&n,&m);m++;
for (int i=0;i<n;i++)c[read()]++;
inv[0]=inv[1]=1;
for (int i=2;i<m;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for (int i=0;i<m;i++)
if (c[i])
for (int j=i;j<m;j+=i)
f[j]=(f[j]+inv[j/i]*c[i])%mod;
exp(f,m);
for (int i=1;i<m;i++)
printf("%lld\n",f[i]);
return 0;
}
```
- **附** : $Eular(F(x))=\exp\bigg(\sum\limits_{i=1}\dfrac{F(x^i)}{i}\bigg)$
其实就是这道题的正解人话换成了公式。
$$Eular(F(x))=\exp\sum\limits_{i=0}\ln\Big(\dfrac{1}{1-x^i}\Big)^{F[i]}$$
$$=\exp\sum\limits_{i=0}F[i]\sum\limits_{j=1}\dfrac{x^{ij}}{j}$$
$$=\exp\sum\limits_{j=1}\frac{1}{j}\sum\limits_{i=0}F[i]x^{ij}$$
$$=\exp\bigg(\sum\limits_{i=1}\frac{F(x^i)}{i}\bigg)$$
更多技巧请见[Link](https://www.luogu.com.cn/blog/command-block/post-shuo-xue-ji-lu-p5900-wu-biao-hao-wu-gen-shu-ji-shuo)