写的时候有个地方忘取模调了半天【流汗】
先和子集卷积一样处理出 size 那一维,先对集合幂级数那一维 fmt,然后在形式幂级数那一维作 \(\mathcal{O}(n^2)\) 的暴力 ln, exp。
写的时候遇到的坑点是集合幂级数那一维的范围其实是 \([0,n]\) 而不是 \([0,n-1]\)。
void fmt(int *f,int n,int op){
for(int i=0;i<n;i++){
if(op==1){
for(int j=0;j<bit(n);j++)
if(j&bit(i))
cadd(f[j],f[j-bit(i)]);
}
else{
for(int j=bit(n)-1;j>=0;j--)
if(j&bit(i)){
cdel(f[j],f[j-bit(i)]);
}
}
}
}
void fmtln(int *f,int n){
static int a[16][(1<<15)+10];
for(int i=0;i<=n;i++)for(int j=0;j<bit(n);j++)a[i][j]=0;
for(int i=0;i<bit(n);i++)a[__builtin_popcount(i)][i]=f[i];
for(int i=0;i<=n;i++)fmt(a[i],n,1);
for(int S=0;S<bit(n);S++){
static int b[16];
for(int i=0;i<n;i++){
int s=1ll*(i+1)*a[i+1][S]%mod;
for(int j=1;j<=i;j++)cdel(s,1ll*a[j][S]*b[i-j]%mod);
b[i]=s;
}
for(int i=1;i<=n;i++)a[i][S]=1ll*b[i-1]*iv[i]%mod;
}
for(int i=0;i<=n;i++)fmt(a[i],n,-1);
for(int i=0;i<bit(n);i++)f[i]=a[__builtin_popcount(i)][i];
}
void fmtexp(int *f,int n){
static int a[16][(1<<15)+10];
for(int i=0;i<=n;i++)for(int j=0;j<bit(n);j++)a[i][j]=0;
for(int i=0;i<bit(n);i++)a[__builtin_popcount(i)][i]=f[i];
for(int i=0;i<=n;i++)fmt(a[i],n,1);
for(int S=0;S<bit(n);S++){
static int b[16];
for(int i=0;i<=n;i++){
int s=0;
if(i<n)s=1ll*(i+1)*a[i+1][S]%mod;
for(int j=1;j<=i;j++)cadd(s,1ll*a[i-j+1][S]*(i-j+1)%mod*b[j-1]%mod*iv[j]%mod);
b[i]=s;
}
for(int i=1;i<=n;i++)a[i][S]=1ll*b[i-1]*iv[i]%mod;
}
for(int i=0;i<=n;i++)fmt(a[i],n,-1);
for(int i=0;i<bit(n);i++)f[i]=a[__builtin_popcount(i)][i];
}
标签:exp,ln,幂级数,int,一维,集合
From: https://www.cnblogs.com/do-while-true/p/18140667