叠甲:读者很菜。
集合幂级数是一个很厉害的东西。
我们对于是有限集的全集
一般记为
对于占位符的运算,有
子集卷积
我们考虑最基本的卷积运算:
已知
【模板】子集卷积
如果运算有
但是并不是,只有在
我们知道
所以我们添加一个占位符
具体的实现,就是增加以为,这一位的运算是朴素的多项式卷积。
多项式卷积使用暴力算法可以做到
void mul(int *F,int *G,int *H)
{
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(int i=0;ifor(int i=0;i<=n;i++) FMT(f[i]),FMT(g[i]);
for(int S=0;Sfor(int i=n;~i;i--)
{
g[i][S]=1ll*g[i][S]*f[0][S]%Mod;
for(int j=1;j<=i;j++)
add(g[i][S],1ll*f[j][S]*g[i-j][S]%Mod);
}
}
for(int i=0;i<=n;i++) iFMT(g[i]);
for(int i=0;i
子集卷积 exp
我们来考虑上面卷积运算的一些组合意义:
如果我们想要查询有
依此类推选择
我们考虑选择若干个不交集合(考虑可以不选),有
发现
因此,还是在
所以
所以
而子集卷积 exp 的组合意义就是:选择若干个不交集合组合在一起的所有方案。
void exp(int *F,int *G)
{
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(int i=1;ifor(int i=0;i<=n;i++) FMT(f[i]);
for(int S=0,tmp;S0][S]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
add(g[i][S],1ll*j*f[j][S]%Mod*g[i-j][S]%Mod);
g[i][S]=1ll*g[i][S]*inv[i]%Mod;
}
}
for(int i=0;i<=n;i++) iFMT(g[i]);
for(int i=0;i
子集卷积 ln
有 exp 就自然会有 ln。
既然 exp 是组合,那么 ln 就是拆分。
exp 是已知
由于
这样实现的复杂度也是
组合意义就是:拆分成若干个不交集合。
void ln(int *F,int *G)
{
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(int i=1;i0][0]=1;
for(int i=0;i<=n;i++) FMT(f[i]);
for(int S=0,tmp;Sfor(int i=1;i<=n;i++)
{
g[i][S]=f[i][S],tmp=0;
for(int j=1;jadd(tmp,1ll*j*g[j][S]%Mod*f[i-j][S]%Mod);
del(g[i][S],1ll*tmp*inv[i]%Mod);
}
}
for(int i=0;i<=n;i++) iFMT(g[i]);
for(int i=0;i