集合幂级数

定义

我们有时候想要刻画一个集合以及它的所有子集的状态。类似形式幂级数将序列对应为一个多项式，我们可以用这种方法把集合对应为一个多项式，对于全集 $U$，标准的集合幂级数定义如下：

$$F(x)=\sum_{S\in 2^U} f_S x^S$$

为了方便表述，上式中的 $2^U$ 定义为 $U$ 的所有子集组成的集合。

这个形式类似于形式幂级数 $\sum_{i}f_ix^i$（感觉形式幂级数最经典的应用应该是生成函数？），所以 $x^S$ 和 $x^i$ 的性质是相同的，它们都是一个占位符，当它单独出现的时候没有意义，所以只能写 $cx^S$ 而不能写 $c\times x^S$，$cx^S$ 表示集合为 $S$ 且 $f_S$ 对应的值为 $c$。

运算

我们定义集合幂级数的运算。

首先加减法是简单的， 若 $f,g$ 对应的全集 $U$ 相同且有集合幂级数 $h=f+g$，则 $h_S=f_S+g_S$。

对于乘法，我们考虑集合幂级数 $\displaystyle h=f\cdot g=\Big(\sum_{L\in 2^U}f_L x^L\Big)\cdot\Big(\sum_{R\in 2^U}g_Rx^R\Big)=\sum_{L\in2^U}\sum_{R\in 2^U}f_Lx^L\cdot g_Rx^R$。

然后我们考虑怎么定义 $f_Lx^L\cdot g_R x^R$，设其结果为 $(f_L\times g_R) x^{L*R}$，其中 $*$ 是 $2^U$ 上的二元运算。

（二元运算即只涉及两个元素和一个操作符的运算，具有封闭性，并具有交换律和结合律，一定有单位元。这里是我们希望集合幂级数的乘法满足乘法交换律和乘法结合律）。

则我们要求进行乘法的集合需要满足一些性质，$*$ 满足交换律和结合律，且 $*$ 有单位元 $\varnothing$。

显然满足上述条件的 $*$ 不唯一，于是集合幂级数的乘法运算也不唯一。

常见的 $*$ 有集合并，集合交，集合对称差，子集卷积。

对应到位运算卷积中的或卷积，与卷积，异或卷积，子集卷积。

集合并卷积

我们将 $*$ 定义为 $\cup$：

$$h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\cup R=S]f_Lg_R$$

（即两个并为 $S$ 的集合 $L,R$ 相乘后会贡献到 $S$ 上）。

从位运算的角度看就是 $\displaystyle h_i=\sum_{j|k=i}f_jg_k$。

下面我们用位运算卷积的角度来考虑如何求解，对应到位运算卷积中相当于或卷积：

我们直接卷积复杂度是 $\mathcal{O}(4^n)$ 的。

然后这里用的是位运算在每一位的独立性来证明分治求解的正确性。

我们设 $f=f^-+x^{\set{n}}\cdot f^+,g=g^-+x^{\set{n}}\cdot g^+$。

$f^-$ 表示 $f$ 不包含元素 $n$ 的所有集合对应的集合幂级数，$\displaystyle f^-=\sum_{n\not\in S} f_Sx^S=\sum_{0\le i< 2^{n-1}}f_ix_i$，

$f^+$ 包含元素 $n$ 的所有的集合对应的集合幂级数，同时将集合中的元素 $n$ 除去但是保留 $f_S$（于是相当于把 $x^{\set{n}}$ 提出来），有：$\displaystyle f^+=\sum_{n\in S}f_Sx^{S/\set{n}}=\sum_{2^{n-1}\le i<2^n} f_ix^{i-2^{n-1}}$。

注意到 $f^-,f^+$ 的大小都是 $2^{n-1}$，即 $f$ 的大小的一半。

于是 $f\cdot g=(f^-+x^{\set{n}}\cdot f^+)\cdot(g^-+x^{\set{n}}\cdot g^+)$，有 $x^{\set{n}}\cdot x^{\set{n}}=x^{\set{n}}$（因为 $x^S$ 是占位符，代表当前集合是什么，进行当前的 $*$ 运算，而 $\set{n}\cup \set{n}=\set{n}$），则：

$f\cdot g=f^-\cdot g^-+x^{\set{n}}\cdot((f^-+f^+)\cdot (g^-+g^+)-f^-\cdot g^-)$。

于是拆成了可以由两个大小为 $2^{n-1}$ 的集合幂级数的集合并卷积（$f^-\cdot g^-$ 和 $(f^-+f^+)\cdot (g^-+g^+)$）表示的式子，继续递归下去。

（前半部分的式子给不包含 ${n}$ 的集合贡献，后半段给包含 $n$ 的集合贡献）。

可以得到时间复杂度的式子 $\mathcal{T}(n)=2\mathcal{T}(\frac{n}{2})+\mathcal{O}(n)$。

根据主定理有 $T(n)=\mathcal{O}(n\log n)$，带入 $n$ 个元素的集合的全集大小 $2^n$，上述分治做法的时间复杂度为 $\mathcal{O}(n2^n)$。

此时理论复杂度已经很优了，但是因为赋值和累加数组的操作，这个做法常数是非常大的，我们考虑优化。

我们考虑在递归的每一层中，数组的后半部分的操作的实质（即包含 $n$ 的集合，$2^{n-1}+1$ 到 $2^n$，它们的二进制的第 $n$ 位为 $1$），我们相当于先将 $f_i$ 加上 $f_{i-2^{n-1}}$ 进行相乘，最后再减去 $f_{i-2^{n-1}}$ 相乘的结果。

于是我们考虑模拟递归的过程，从大到小枚举每一位 $j(1\le j\le n)$，对所有第 $j$ 位为 $1$ 的数 $i$，令 $f_i\leftarrow f_i+f_{i-2^{j-1}},g_i\leftarrow g_i+g_{i-2^{j-1}}$，于是我们得到了两个新的集合幂级数 $\hat{f}$ 和 $\hat{g}$，我们令 $\hat{h}$ 为 $\hat{f},\hat{g}$ 在对应位置系数相乘后得到的集合幂级数（注意这里不是卷积），于是再次从小到大枚举 $j$，则 $\hat{h}_i=\hat{h}_i-\hat{h}_{i-2^{j-1}}$，得到 $h$，$h$ 即为 $f\cdot g$。

然后我们发现其实枚举 $j$ 的顺序不会对 $f,g$ 的取值产生任何影响。

于是有：

$$\hat{f}_i=\sum_{j|i=i}f_j \hat{f}_S=\sum_{T\sube S}f_T\\$$

对于集合幂级数，我们称形如 $\hat{f}_i=\sum_{j|i=i}f_j$ 的变换为莫比乌斯变换。 记作 $FMT(f)$。

考虑 $\hat{h}_i\leftarrow \hat{h}_i-\hat{h}_{i-2^{j-1}}$，不难发现对于 $T\sube S$，$\hat{h}_T$ 对 $h_S$ 的贡献系数为 $(-1)^{|S|-|T|}$，根据容斥原理可以得到这个结果。

所以对于集合幂级数 $f$，我们称形如 $\hat{f}_i=\sum_{j|i=i}(-1)^{popcount(i)-popcount(j)}f_j$ 的变换为莫比乌斯反演，记作 $FMI(f)$。

FMT 和 FMI 互为逆运算。

所以我们枚举 $j$，把 $j$ 位置上是 $0$ 的值加到 $j$ 位置上是 $1$ 的值上：

于是通式为 $f_i\leftarrow f_i+c\times f_{j-2^{j-1}}$，对于 FMT，$c=1$，对于 FMI ，$c=-1$。

然后是用位运算卷积求解集合卷积的正确性证明：

$h_S=\displaystyle\sum_{L}\sum_{R}[L\cup R=S]f_Lg_R$，因此 $\hat{h}_S=\displaystyle\sum_{L}\sum_{R}[L\cup R\sube S]f_{L}g_R$（二进制中使原本为 $1$ 的位置变为 $0$ 就相当于集合取子集）。

因为 $[L\sube S][R\sube S]=[L\cup R\sube S]$，所以有 $\hat{h}_S=\Big(\sum_{L}[L\sube S]f_L\Big)\times \Big(\sum_{R}[R\sube S]g_R\Big)=\hat{f}_S\times \hat{g}_S$，因为是直接相乘，所以我们直接枚举 $S$，是 $\mathcal{O}(2^n)$ 的。

然后 FMT 和 FMI 的复杂度都是 $\mathcal{O}(n2^n)$，$\mathcal{O}(n)$ 枚举位置 $j$，$\mathcal{O}(2^n)$ 枚举集合 $j$。

于是整体复杂度 $\mathcal{O}(n2^n)$。

集合交卷积

和集合并是一样的，这里直接用集合卷积的形式证明，对应到位运算卷积里就是与卷积：

$h_S=\displaystyle\sum_{L}\sum_{R}[L\cap R=S]f_Lg_R$，因此 $\hat{h}_S=\displaystyle\sum_{L}\sum_{R}[L\cap R\supe S]f_{L}g_R$。

因为 $[L\supe S][R\supe S]=[L\cap R\supe S]$，所以有 $\hat{h}_S=\Big(\sum_{L}[L\supe S]f_L\Big)\times \Big(\sum_{R}[R\supe S]g_R\Big)=\hat{f}_S\times \hat{g}_S$，依旧是直接相乘，时间复杂度 $\mathcal{O}(2^n)$。

然后我们枚举 $j$，把 $j$ 位置上是 $1$ 的值加到 $j$ 位置上是 $0$ 的值上：

通式 $f_i\leftarrow f_i+c\times f_{i+2^{j-1}}$，对于 FMT，$c=1$，对于 FMI，$c=-1$。

集合对称差卷积

定义集合上的二元运算 $\oplus$ 表示 $A\oplus B=\set{x|(x\in A)\oplus (x\in B)}$，后者的 $\oplus$ 表示异或运算，有：

$$h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\oplus R=S]f_Lg_R$$

从位运算的角度理解，就是异或卷积，即 $h_i=\sum_{j\oplus k=i}f_jg_k$。

设 $f=f^-+x^{\set{n}}\cdot f^+,g=g^-+x^{\set{n}}\cdot g^+$，于是有：

$f\cdot g=(f^-+x^{\set{n}} f^+)(g^-+x^{\set{n}}g^+)=(f^-g^-+f^+g^+)+x^{\set{n}}(f^-g^++f^+g^-)$ 。

（因为 $x^{\set{n}}\cdot x^{\set{n}}=x^{\varnothing}$，$\set{n}\oplus \set{n}=\varnothing$）。

如果拆成四个大小为 $2^{n-1}$ 的子卷积，那么复杂度仍是 $\mathcal{O}(4^n)$ 的。

（根据主定理 $\mathcal{T}(n)=4\mathcal{T}(\frac{n}{2})+\mathcal{O}(n)$，那么 $\mathcal{T}(n)=n^2$，带入 $n$ 个元素的集合的全集大小复杂度就是 $\mathcal{O}(4^n)$）。

于是我们考虑计算 $p=(f^-+f^+)(g^-+g^+)$ 以及 $q=(f^-+f^+)(g^-+g^+)$，

那么有 $f\cdot g=\frac{p+q}{2}+x^{\set{n}}\frac{p-q}{2}$，时间复杂度 $\mathcal{O}(n2^n)$。

然后有一个非常神奇的转化：

$\displaystyle[S=\varnothing]=\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}$。

显然当 $S=\varnothing$ 时，$|S\cap T|$ 的值总为 $0$，那么右式的值为 $\displaystyle\frac{1}{2^n}\sum_{T\in 2^U}(-1)^0=\frac{1}{2^n}\sum_{T\in 2^U} 1=1$。

当 $S\not = \varnothing$ 时，我们选择 $S$ 中任意一个元素 $x$，那么显然不包含 $x$ 和包含 $x$ 的 $T$ 一一对应，且和 $S$ 的交集的奇偶性不同，所以会两两抵消，右式的值为 $0$。

注意到 $L\oplus R=S$ 等价于 $L\oplus R\oplus S=\varnothing$，且 $(L\oplus R)\cap S=(L\cap S)\oplus (R\cap S)$，则有：

$$h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\oplus R=S]f_Lg_R\\ =\frac{1}{2^n}\sum_{L\in 2^U}\sum_{R\in 2^U}\sum_{T\in 2^U}(-1)^{|(S\oplus L\oplus R)\cap T|}f_Lg_R\\ =\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}\Big(\sum_{L\in 2^U}(-1)^{|L\cap T|}f_L\Big)\Big(\sum_{R\in 2^U}(-1)^{|R\cap T|}g_R\Big)$$

（关于第二个式子到第三个式子，本来应该拆成 $|(S\oplus L\oplus R)\cap T|=|(S\cap T)\oplus (L\cap T)\oplus (R\cap T)|$ 的，但显然在 $-1$ 的幂次的意义下，这个式子可以等于 $|S\cap T|+ |L\cap T|+ |R\cap T|$，因为乘两次 $-1$ 相当于异或抵消的部分）

于是我们考虑令 $\displaystyle\hat{f}_S=\sum_{T\in 2^U}(-1)^{|S\cap T|}f_T$，它被称为 $f$ 的沃尔什变换，记作 $FWT(f)$。

同理，根据 $\displaystyle[S=\varnothing]=\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}$，我们定义 $\hat{f}$ 的沃尔什逆变换为 $f_S=\displaystyle\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}\hat{f}_T$。

证明沃尔什变换和沃尔什逆变换互逆：

$$f_S=\displaystyle\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}\hat{f}_T\\ =\displaystyle\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|S\cap T|}(\sum_{X\in 2^U}(-1)^{|T\cap X|}f_X)\\ =\sum_{X\in 2^U}f_X\frac{1}{2^n}\sum_{T\in 2^U}(-1)^{|(S\oplus X)\cap T|}\\ =\sum_{X\in 2^U}f_X[S\oplus X=\varnothing]\\ =\sum_{X\in 2^U}f_x[S=X]\\ =f_S$$

我们考虑如何计算沃尔什变换。

观察这个式子：

$\displaystyle\hat{f}_S=\sum_{T\in 2^U}(-1)^{|S\cap T|}f_T$。

我们把它写成位运算卷积的形式，就是 $\hat{f_i}=\sum_{0\le j<2^n}(-1)^{popcount(i\And j)}f_j$。

我们考虑分治，把 $i$ 分为首位为 $0$（$0\sim 2^{n-1}-1$）和首位为 $1$（$2^{n-1}\sim 2^{n}-1$）的两部分，我们把 $j$ 也分为两部分，同样是分首位为 $0$ 和首位为 $1$。

我们令 $(\hat{f}^-)_i$ 表示对 $f$ 的前半部分做 FWT 后第 $i$ 个位置的值，$(\hat{f}^+)_i$ 表示对 $f$ 的后半部分做 FWT 后第 $i$ 个位置的值。

考虑一个首位为 $0$ 的 $i$，发现对于所有的 $j$，最高位不会产生贡献 ，因为 $0\And 0=0\land 0\And 1=0$，于是有：

$$\hat{f}_i=\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)+\Big(\sum_{2^{n-1}\le j<2^n}(-1)^{popcount(i\And j)}f_j\Big)\\ =\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)+\Big(\sum_{0\le j<2^{n-1}}(-1)^{popcount(i\And (j+2^{n-1}))}f_{j+2^{n-1}}\Big)\\ =\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)+\Big(\sum_{0\le j<2^{n-1}}(-1)^{popcount(i\And j)}f_{j+2^{n-1}}\Big)\\ =(\hat{f}^-)_i+(\hat{f}^+)_i$$

考虑一个首位为 $1$ 的 $i+2^{n-1}$，发现对于前半部分的 $j$，最高位不会产生贡献，对于后半部分的 $j$，最高位会产生 $1$ 的贡献，因为 $1\And 0=0\land 1\And 1=1$，于是有：

$$\hat{f}_{i+2^{n-1}}=\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount((i+2^{n-1})\And j)}f_j\Big)+\Big(\sum_{2^{n-1}\le j<2^n}(-1)^{popcount((i+2^{n-1})\And j)}f_j\Big)\\ =\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)+\Big(\sum_{0\le j<2^{n-1}}(-1)^{popcount((i+2^{n-1})\And (j+2^{n-1}))}f_{j+2^{n-1}}\Big)\\ =\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)+\Big(\sum_{0\le j<2^{n-1}}(-1)^{popcount(i\And j)+1}f_{j+2^{n-1}}\Big)\\ =\Big(\sum_{0\le j< 2^{n-1}}(-1)^{popcount(i\And j)}f_j\Big)-\Big(\sum_{0\le j<2^{n-1}}(-1)^{popcount(i\And j)}f_{j+2^{n-1}}\Big)\\ =(\hat{f}^-)_i-(\hat{f}^+)_i$$

于是我们从大到小枚举 $j$，对于满足 $p+2^{j-1}=q$ 的 $(p,q)$（即除了第 $j$ 位都相同），令 $p\leftarrow p+q,q\leftarrow p-q$（实际上 $j$ 的顺序并不重要要因为各位置独立且等价）

（为什么独立且等价是因为我们每次是基于最高位进行分治，然后相当于用两个数中这一位的与对指数做加法，然而在底数上体现为乘法，于是我们计算第 $k$ 位的变换的时候，只关心第 $k$ 位的 $0/1$ 情况，和其他位无关）。

然后沃尔什逆变换相当于沃尔什变换多一个 $\dfrac{1}{2^n}$ 的系数，我们可以在最后统一乘上 $2^n$ 的逆元，但是我们发现我们前面说的算法和递归本质等价，所以我们可以把 $\dfrac{1}{2^n}$ 的系数拆成 $n$ 个 $\dfrac12$ 放进 $n$ 层里面，于是在逆变换的时候每次除以 $2$。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;

const int MAXN = 17 + 3;
const int MR = (1<<17) + 10;
const ll mod = 998244353;
const ll inv2 = (mod+1)/2;

int n,U;
ll A[MR],B[MR];
ll a[MR],b[MR],c[MR];

int main(){
	scanf("%d",&n),U=(1<<n)-1;
	FL(S,0,U) scanf("%lld",&A[S]);
	FL(S,0,U) scanf("%lld",&B[S]);
	FL(S,0,U) a[S]=A[S],b[S]=B[S];
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1)
				a[S]=(a[S]+a[S^(1<<j)])%mod,
				b[S]=(b[S]+b[S^(1<<j)])%mod;
	FL(S,0,U) c[S]=a[S]*b[S]%mod;
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1)
				c[S]=(c[S]-c[S^(1<<j)]+mod)%mod;
	FL(S,0,U) printf("%lld ",c[S]); 
	puts("");
	FL(S,0,U) a[S]=A[S],b[S]=B[S];
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1)
				a[S^(1<<j)]=(a[S^(1<<j)]+a[S])%mod,
				b[S^(1<<j)]=(b[S^(1<<j)]+b[S])%mod;
	FL(S,0,U) c[S]=a[S]*b[S]%mod;
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1)
				c[S^(1<<j)]=(c[S^(1<<j)]-c[S]+mod)%mod;
	FL(S,0,U) printf("%lld ",c[S]); 
	puts("");
	FL(S,0,U) a[S]=A[S],b[S]=B[S];
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1){
				ll x=a[S^(1<<j)],y=a[S];
				a[S^(1<<j)]=(x+y)%mod,a[S]=(x-y+mod)%mod;
				x=b[S^(1<<j)],y=b[S];
				b[S^(1<<j)]=(x+y)%mod,b[S]=(x-y+mod)%mod;
			}
	FL(S,0,U) c[S]=a[S]*b[S]%mod;
	FL(j,0,n-1)
		FL(S,0,U)
			if((S>>j)&1){
				ll x=c[S^(1<<j)],y=c[S];
				c[S^(1<<j)]=(x+y)%mod*inv2%mod,c[S]=(x-y+mod)%mod*inv2%mod;
			}
	FL(S,0,U) printf("%lld ",c[S]); 
	puts("");
}

子集卷积

定义集合之间的二元运算为不相交集的合并，即 $x^L\cdot x^R=\begin{cases}0,(L\cap R\not = \varnothing)\\x^{L\cup R},(L\cap R=\varnothing)\end{cases}$，我们得到了子集卷积的形式。

$$h_S=\sum_{L\in 2^U}\sum_{R\in 2^U}[L\cup R=S][L\cap R=\varnothing]f_Lg_R$$

我们可以暴力枚举子集做到 $\mathcal{O}(3^n)$，我们枚举 $S$，枚举 $S$ 的子集 $L$，则 $R=\complement_SL$。

注意到当 $L\cup R=S$ 时，$L\cap R=\varnothing$ 的充要条件是 $|L|+|R|=|S|$，因此我们设 $f_{i,S}=[|S|=i]f_S,g_{i,S}=[|S|=i]g_S$。

令 $H_i=\sum_{j+k=i}f_j\cdot g_k$（$H_i$ 是一个集合幂级数，$H_{i,S}=[L\cup R=S]f_{j,L}f_{k,R}$，$\cdot$ 表示对 $f_j,g_k$ 做集合并卷积，因为 $j+k=i$，所以 $L,R$ 必定交集为空，所以根据定义就满足二元运算的条件）。

两边同时取 FMT，有 $\hat{H}_i=\sum_{j+k=i}\hat{f}_j\cdot \hat{g}_k$（注意做了 FMT 之后就可以对应位置系数相乘了，所以复杂度是 $\mathcal{O}(n^22^n)$，枚举 $i,k,S$）。

我们 $\mathcal{O}(2^n)$ 计算出 $f_{i,S}/g_{i,S}$，然后 $\mathcal{O}(n2^n)$ 对其做 FMT/FMI，所以复杂度瓶颈在相乘，最后把 $H_{|S|,S}$ 累进答案，总时间复杂度 $\mathcal{O}(n^22^n)$。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 20 + 5;
const int MR = (1<<20) + 5;
const ll mod = 1e9 + 9;

int n,U;
ll a[MAXN][MR],b[MAXN][MR],c[MAXN][MR];

int main(){
	scanf("%d",&n),U=(1<<n)-1;
	FL(S,0,U) scanf("%lld",&a[__builtin_popcount(S)][S]);
	FL(S,0,U) scanf("%lld",&b[__builtin_popcount(S)][S]);
	FL(i,0,n)
		FL(j,0,n-1)
			FL(S,0,U)
				if((S>>j)&1)
					a[i][S]=(a[i][S]+a[i][S^(1<<j)])%mod,
					b[i][S]=(b[i][S]+b[i][S^(1<<j)])%mod;
	FL(S,0,U)
		FL(j,0,n)
			FL(k,0,n-j)
				c[j+k][S]=(c[j+k][S]+a[j][S]*b[k][S]%mod)%mod;
	FL(i,1,n)
		FL(j,0,n-1)
			FL(S,0,U)
				if((S>>j)&1)
					c[i][S]=(c[i][S]-c[i][S^(1<<j)]+mod)%mod;
	FL(S,0,U) printf("%lld ",c[__builtin_popcount(S)][S]);
} 

---

（此处本应有十几道例题）

另：例题想要的可以私信我，整理起来很麻烦就懒了。