$O(3^n)$就是简单枚举子集。
设$p[i]=i的二进制个数$,
想成一个矩阵,也就是$c_{p(m)}$也就是$a_{p(i)},b_{p(j)}$这两行$FWT$或一下。然后我们枚举行即可。复杂度$O(n^22^n)$
P6097 【模板】子集卷积
1 |
|
$O(3^n)$就是简单枚举子集。
设$p[i]=i的二进制个数$,
想成一个矩阵,也就是$c_{p(m)}$也就是$a_{p(i)},b_{p(j)}$这两行$FWT$或一下。然后我们枚举行即可。复杂度$O(n^22^n)$
1 | #include <bits/stdc++.h> |