其实是半在线子集卷积模板。
算法简介
半在线子集卷积用来处理形如 \(f_S=\sum\limits_{T\subseteq S}f_Tg_{S-T}\) 的卷积。
与子集卷积相同地，我们设 \(F_{i,S}=[|S|=i]f_S,G_{i,S}=[|S|=i]g_S\)，然后按照 \(i\) 从小到大得到 \(f\) 的值。现在，假设 \(|S|<i\) 的所有 \(f_S\) 已被求出，考虑如何求一个 \(|S|=i\) 的 \(f_S\)。如果暴力地做，直接枚举子集转移，复杂度 \(O(3^n)\)，不能接受。我们对 \(j<i\) 的所有 \(F_{j},G_{j}\) 做高维前缀和，得到 \(\text{FWT}(F)_{i},\text{FWT}(G)_{i}\)，然后就会发现 \(\text{FWT}(F)_{i,S}=\sum\limits_{T\subseteq S}[|T|=i]sum_{i,T}\)，对于 \(\text{FWT}(G)\) 同理。于是 \(\text{FWT}(F)_{i,S}=\sum\limits_{j\le i}\text{FWT}(F)_{i-j,S}\text{FWT}(G)_{j,S}\)，就可以 \(O(n)\) 转移了。
复杂度分析
对于每个 \(i,S\)，\(F_{i,S}\) 需要 \(O(n)\) 时间得到，需要 \(O(n)\) 次 FWT，总复杂度 \(O(2^nn^2)\)。居然和普通子集卷积的复杂度一样！
思路
直接看题目给的式子 \(F(x)G(x)=1\)。设 \(f_S=[x^S]F(x),g_S=[x^S]G(x)\)，则有
令 \(S=\varnothing\)，可得 \(g_\varnothing f_\varnothing=1\)。
现在设 \(S\not=\varnothing\)，则：
然后就是一个半在线子集卷积。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int N=20,mod=998244353;
int n,f[N+1][1<<N],g[N+1][1<<N];
long long qpow(long long x,int y=mod-2){long long ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;
}
void FWT(int *f,int n,int rev=0){for(int w=1;w<n;w<<=1)for(int i=0;i<n;i+=w<<1)for(int j=0;j<w;j++)if(rev)f[i+j+w]-=f[i+j],f[i+j+w]<0&&(f[i+j+w]+=mod);else f[i+j+w]+=f[i+j],f[i+j+w]>=mod&&(f[i+j+w]-=mod);
}
signed main(){clock_t _st=clock();ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<1<<n;i++)cin>>f[__builtin_popcount(i)][i];g[0][0]=qpow(f[0][0]);FWT(g[0],1<<n),FWT(f[0],1<<n);for(int i=1,inv=mod-g[0][0];i<=n;i++){FWT(f[i],1<<n);for(int j=1;j<=i;j++)for(int s=0;s<1<<n;s++)g[i][s]=(g[i][s]+1ll*g[i-j][s]*f[j][s])%mod;FWT(g[i],1<<n,1);for(int s=0;s<1<<n;s++)g[i][s]=1ll*g[i][s]*inv%mod;FWT(g[i],1<<n);}for(int i=0;i<=n;i++)FWT(g[i],1<<n,1);for(int i=0;i<1<<n;i++)cout<<g[__builtin_popcount(i)][i]<<' ';cout<<'\n';clock_t _ed=clock();cerr<<(_ed-_st)*1.0/CLOCKS_PER_SEC<<'\n';return 0;
}