//好吧标题是扯蛋的

1. 啥是集合卷积

$C _ k = \sum _ {i + j = k} A _ i \times B _ j$

$C _ k = \sum _ {i | j = k} A _ i \times B _ j$

2. 或卷积

$C _ k = \sum _ {i | j = k} A _ i \times B _ j$

$F’ _ i=\sum _ {j\subseteq i} F _ j$

$C _ k = \sum _ {i | j = k} A _ i \times B _ j$

$A’ _ i = \sum _ {j\subseteq i} A _ j$

$B’ _ i = \sum _ {j\subseteq i} B _ j$

$C’ _ i = \sum _ {j\subseteq i} C _ j$

$A’ _ i \times B’ _ i = \sum _ {m\subseteq i} A _ m \times \sum _ {n\subseteq i} B _ n = \sum _ {(m | n) \subseteq i} A _ m \times B _ n = C’ _ i$

QwQ

（TMD 刚刚不小心按到刷新键了刚写的全没了沃日。。。）

$L’ _ i = \sum _ {j\subseteq i} F _ j(i < \frac N 2)$

$R’ _ i = \sum _ {j\subseteq i} F _ {j + \frac N 2}(i < \frac N 2)$

$F’ = \{ L’ \},\{ R’ + L’ \}$

（网上很多逆变换说得云里雾里看不懂什么鬼。。。）

$F _ i = \sum _ {j \subseteq i} F’ _ j \times (-1) ^ {bitcount(i – j)}$

（就是原本的 $R’ _ i + L’ _ i$变成了 $R _ i + (- L _ i)$）

void FMT_OR(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
if (f == 1) a[j + l] = pls(a[j + l], a[j]);
else a[j + l] = mns(a[j + l], a[j]);
}


3. 与卷积

a & b = !((!a) | (!b))

$F’ _ i=\sum _ {j\supseteq i} F _ j$

$F’ = \{ L’ + R’ \},\{ L’ \}$

emmmm… 逆向变换就是：

$F’ = \{ L’ – R’ \},\{ L’ \}$

void FMT_AND(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
if (f == 1) a[j] = pls(a[j], a[j + l]);
else a[j] = mns(a[j], a[j + l]);
}


4. 异或卷积

（或者说是他也不会证）

（然而实际上和 FMT 没啥区别，只不过发明的人不同而已。。。）

（而且长得都一样，只不过把中间的字母倒过来了）

$F’=\{ L’ + R’ \},\{ L’ – R’ \}$

$F=\{ \frac {L + R} {2} \},\{ \frac {L – R} {2} \}$

void FWT_XOR(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i, t1, t2; j < i + l; j += 1)
{
t1 = a[j], t2 = a[j + l];
a[j] = pls(t1, t2), a[j + l] = mns(t1, t2);
if (f == -1) a[j] = mul(a[j], IV2), a[j + l] = mul(a[j + l], IV2);
}
}


5. 子集卷积

（$bitcount(a)$依然是上文提到的数二进制下 $1$的个数）

$C _ {bitcount(k), k} = \sum _ {i \cup j = k \& \& bitcount(i) + bitcount(j)=bitcount(k)} A _ {bitcount(i), i} \times B _ {bitcount(j), j}$

$C _ {bitcount(k), k} = \sum _ {i \cup j = k} A _ {bitcount(i), i} \times B _ {(bitcount(k) – bitcount(i)), j}$

6. 例题

1. Hard Nim BZOJ – 4589

#include <bits/stdc++.h>

#define P (1000000007)
#define MS (150005)
#define IV2 (500000004)

using namespace std;

int pls(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int mns(int a, int b) {return a - b < 0 ? a - b + P : a - b;}
int mul(int a, int b) {return 1ll * a * b % P;}

int n, m, prm[MS], pnt, p[MS], res[MS];

bool ntp[MS];

void FWT(int (&a)[MS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i, t1, t2; j < i + l; j += 1)
{
t1 = a[j], t2 = a[j + l];
a[j] = pls(t1, t2), a[j + l] = mns(t1, t2);
if (f == -1) a[j] = mul(a[j], IV2), a[j + l] = mul(a[j + l], IV2);
}
}

int main(int argc, char const* argv[])
{
for (int i = 2; i <= MS - 5; i += 1)
{
if (!ntp[i]) prm[++pnt] = i;
for (int j = 1, k; j <= pnt; j += 1)
{
k = i * prm[j];
if (k > MS - 5) break;
ntp[k] = 1;
if (i % prm[j] == 0) break;
}
}
while (~scanf("%d%d", &n, &m))
{
memset(p, 0, sizeof(p));
for (int i = 2; i <= m; i += 1) p[i] = !ntp[i];
int N = 1; while (N <= m) N <<= 1;
FWT(p, N, 1);
for (int i = 0; i < N; i += 1) res[i] = 1;
while (n)
{
if (n & 1) for (int i = 0; i < N; i += 1) res[i] = mul(res[i], p[i]);
for (int i = 0; i < N; i += 1) p[i] = mul(p[i], p[i]);
n >>= 1;
}
FWT(res, N, -1), printf("%d\n", res[0]);
}
return 0;
}


2.【模板】快速沃尔什变换 LUOGU – 4717

#include <bits/stdc++.h>

#define P (998244353)
#define NS (200000)
#define IV2 (499122177)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int pls(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int mns(int a, int b) {return a - b < 0 ? a - b + P : a - b;}
int mul(int a, int b) {return 1ll * a * b % P;}

void FMT_OR(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
if (f == 1) a[j + l] = pls(a[j + l], a[j]);
else a[j + l] = mns(a[j + l], a[j]);
}

void FMT_AND(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
if (f == 1) a[j] = pls(a[j], a[j + l]);
else a[j] = mns(a[j], a[j + l]);
}

void FWT_XOR(int (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i, t1, t2; j < i + l; j += 1)
{
t1 = a[j], t2 = a[j + l];
a[j] = pls(t1, t2), a[j + l] = mns(t1, t2);
if (f == -1) a[j] = mul(a[j], IV2), a[j + l] = mul(a[j + l], IV2);
}
}

int N, bs, A[NS], B[NS], C[NS];

int main(int argc, char const* argv[])
{
IN(bs), N = (1 << bs);
for (int i = 0; i < N; i += 1) IN(A[i]);
for (int i = 0; i < N; i += 1) IN(B[i]);
// or
FMT_OR(A, N, 1), FMT_OR(B, N, 1);
for (int i = 0; i < N; i += 1) C[i] = mul(A[i], B[i]);
FMT_OR(C, N, -1);
for (int i = 0; i < N; i += 1) printf("%d ", C[i]);
putchar(10), FMT_OR(A, N, -1), FMT_OR(B, N, -1);
// and
FMT_AND(A, N, 1), FMT_AND(B, N, 1);
for (int i = 0; i < N; i += 1) C[i] = mul(A[i], B[i]);
FMT_AND(C, N, -1);
for (int i = 0; i < N; i += 1) printf("%d ", C[i]);
putchar(10), FMT_AND(A, N, -1), FMT_AND(B, N, -1);
// xor
FWT_XOR(A, N, 1), FWT_XOR(B, N, 1);
for (int i = 0; i < N; i += 1) C[i] = mul(A[i], B[i]);
FWT_XOR(C, N, -1);
for (int i = 0; i < N; i += 1) printf("%d ", C[i]);
return 0;
}


3. [HAOI2015] 按位或 BZOJ – 4036

$Ans = \sum _ {i = 1} ^ \infty i\times (P ^ i – P ^ {i – 1})$

（注意这里只对询问取到 $2 ^ n – 1$有效，因为如果在第 $i$次之前就得到了 $2 ^ n – 1$，那么后面无论选任何数，得到的都依然是 $2 ^ n – 1$，也就是如果在第 $i$次前得到了 $2 ^ n – 1$，那么到第 $i$次，这种情况下得到 $2 ^ n – 1$的概率是 $1$。而对于别的数字则不一定。）

$Ans = P +2P ^ 2 – 2P + 3P ^ 3 – 3P ^ 2… + \infty P ^ \infty – \infty P ^ {\infty – 1}$

$= – P – P ^ 2 – P ^ 3 – … – P ^ {\infty – 1} + \infty P ^ \infty$

$Ans = (1 – P) + (1 – P ^ 2) + (1 – P ^ 3) + … + (1 – P ^ {\infty – 1}) + 1$

$Ans = 1 – \frac {P} {P – 1}$

（最后说一下其实这个貌似用 min-max 容斥会好想很多。。。）

#include <bits/stdc++.h>

#define NS (1 << 20)
#define lowbit(a) (a & -a)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

void FMT(double (&a)[NS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
a[j + l] = a[j + l] + f * a[j];
}

int N, bs, rem;

double p[NS];

int main(int argc, char const* argv[])
{
IN(bs), N = (1 << bs);
for (int i = 0; i < N; i += 1)
{
scanf("%lf", &p[i]);
if (p[i] > 0)
{
int j = i;
while (j) rem |= lowbit(j), j -= lowbit(j);
}
}
if (rem != N - 1) puts("INF"), exit(0);
FMT(p, N, 1);
for (int i = 0; i < N - 1; i += 1) p[i] = p[i] / (p[i] - 1);
p[N - 1] = 0, FMT(p, N, -1);
printf("%.8f", p[N - 1] + 1);
return 0;
}


4. [WC2018] 州区划分 BZOJ – 5153

（这里的小写 $p$是题目给出的 $p$次方）

$F _ s = \frac {1} {P _ s ^ p} \sum _ {T \subseteq S} F _ {S – T} \times G _ T ^ p$

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define P (998244353)
#define NS (22)
#define PS (1 << 21)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int pls(int a, int b) {return a + b >= P ? a + b - P : a + b;}
int mns(int a, int b) {return a - b < 0 ? a - b + P : a - b;}
int mul(int a, int b) {return 1ll * a * b % P;}

int qpow(int a, int b)
{
int res = 1; a %= P;
while (b)
{
if (b & 1) res = mul(res, a);
a = mul(a, a), b >>= 1;
}
return res;
}

void FMT(int (&a)[PS], int N, int f)
{
for (int l = 1; l < N; l <<= 1)
for (int i = 0; i < N; i += (l << 1))
for (int j = i; j < i + l; j += 1)
if (f == 1) a[j + l] = pls(a[j + l], a[j]);
else a[j + l] = mns(a[j + l], a[j]);
}

int n, m, p, w[NS], bc[PS], fa[NS], sum[PS], iv[PS], fum[NS][PS], f[NS][PS];

bool g[NS][NS];

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(p);
for (int i = 1, a, b; i <= m; i += 1)
IN(a), IN(b), a--, b--, g[a][b] = g[b][a] = 1;
for (int i = 0; i < n; i += 1) IN(w[i]);
for (int i = 1; i < (1 << n); i += 1)
{
bc[i] = bc[i >> 1] + (i & 1);
for (int j = 0; j < n; j += 1)
if ((i >> j) & 1) sum[i] = pls(sum[i], w[j]);
sum[i] = qpow(sum[i], p), iv[i] = qpow(sum[i], P - 2);
if (bc[i] == 1) continue;
for (int j = 0, deg; j < n; j += 1) if ((i >> j) & 1) fa[j] = j;
for (int j = 0, deg; j < n; j += 1)
if ((i >> j) & 1)
{
deg = 0;
for (int k = 0; k < n; k += 1)
if (g[j][k] && ((i >> k) & 1)) deg++, fa[findf(k)] = findf(j);
if (deg & 1) {fum[bc[i]][i] = sum[i]; goto end;}
}
for (int j = 0, cnt = 0; j < n; j += 1)
if (((i >> j) & 1) && fa[j] == j)
if (++cnt == 2) {fum[bc[i]][i] = sum[i]; goto end;}
end : continue;
}
f[0][0] = 1, FMT(f[0], 1 << n, 1);
for (int i = 1; i <= n; i += 1) FMT(fum[i], 1 << n, 1);
for (int i = 1; i <= n; i += 1)
{
for (int j = 0; j < i; j += 1)
for (int k = 0; k < (1 << n); k += 1)
f[i][k] = pls(f[i][k], mul(f[j][k], fum[i - j][k]));
FMT(f[i], 1 << n, -1);
for (int j = 0; j < (1 << n); j += 1)
if (bc[j] == i) f[i][j] = mul(f[i][j], iv[j]);
else f[i][j] = 0;
if (i != n) FMT(f[i], 1 << n, 1);
}
printf("%d\n", f[n][(1 << n) - 1]);
return 0;
}


2 条评论

XZYQvQ · 2018年8月21日 8:43 上午

突然开% 猝不及防

其实之前想 fAke 您的都忍住了 OvO