Trick 8：子集卷只因的 SOSDP 做法

问题引入：对于两个数组 \(a\)，\(b\)，长度为 \(2^n\)，从 \(0\) 开始标号。

求 \(c_i = \sum\limits_{p \& q = i} a_pb_q\)。

关于这个问题的求解，我们可以使用 SOSDP 完成一系列 无重计数 以及 容斥 的操作。

首先，我们考虑这个会重的计数：\(c_i = \sum\limits_{i \subseteq p,q} a_pb_q\)

这个其实只要计算 \(a'_i = \sum \limits_{k \subseteq i} a_k\) 然后直接每一位乘起来即可。

然后我们发现，去掉重复的也可以用 SOSDP。那么做完了。\(\mathcal{O}(n2^n)\)

这个问题是解决了，考虑这样一个更实用的问题：如果要求满足 \(\text{popcnt}(p) + \text{popcnt}(q) = \text{popcnt}(i), p | q = i\)，还能套用刚才的吗？

可以！加一维度表示维护的 \(\text{popcnt}\)。这个 trick 在我写那个啥生成树计数的时候本来可以用上的，但是复杂度寄了点（）这里用上了。时间复杂度 \(\mathcal{O}(n^22^n)\)。

void add(ll &a,ll b){
	a += b;
	if(a>=mod) a-=mod;
}
ll n, a[21][1048576], b[21][1048576], c[21][1048576];
void solve() {
    n = read();
    for (ll i = 0; i < (1 << n); i++) a[__builtin_popcount(i)][i] = read();
    for (ll i = 0; i < (1 << n); i++) b[__builtin_popcount(i)][i] = read();
    for(ll k = 0; k <= n; k ++)
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < (1 << n); j++) {
            if (j & (1 << i)) {
                add(a[k][j],a[k][j ^ (1 << i)]);
        	}
        }
    for(ll k = 0; k <= n; k ++)
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < (1 << n); j++) {
            if (j & (1 << i)) {
                add(b[k][j],b[k][j ^ (1 << i)]);
        	}
        }
		for(ll k = 0; k <= n; k ++)
			for(ll l = 0; k+l <= n; l ++)
				for (ll i = 0; i < (1 << n); i++) add(c[k+l][i] , 1ll * a[k][i] * b[l][i] % mod);
				// 注意，k,l 放在循环前面，可以保证数组下标访问的连续性以减少常数。
	for(ll k = 0; k <= n; k ++)
    for (ll i = 0; i < n; i++)
        for (ll j = (1 << n) - 1; j >= 0 ; j --) {
            if (j & (1 << i)) {
                add(c[k][j] ,(mod - c[k][j - (1 << i)]));
            }
        }
    for (ll i = 0; i < (1 << n); i++) printf("%d ", c[__builtin_popcount(i)][i]);
}