快速入门

记公式：

Or operation:

    arr[k + step] += opt * arr[k]

And operation:

    arr[k] += opt * arr[k + step]

Xor operation:

    A = arr[k], B = arr[k + step]

    arr[k] = A + B, arr[k + step] = A - B

    with inverse-operation, the inv2 is needed:

    arr[k] /= 2, arr[k + step] /= 2;

// P4717.cpp
// NTT;
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = (1 << 17) + 200, mod = 998244353;

int n, Ai[MAX_N], Bi[MAX_N], C[MAX_N], A[MAX_N], B[MAX_N];

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int inv2 = quick_pow(2, mod - 2);

void fwt_or(int *arr, int opt)
{
    for (int step = 1; step < n; step <<= 1)
        for (int j = 0; j < n; j += (step << 1))
            for (int k = j; k < j + step; k++)
                arr[k + step] = (1LL * arr[k + step] + mod + 1LL * arr[k] * opt) % mod;
}

void fwt_and(int *arr, int opt)
{
    for (int step = 1; step < n; step <<= 1)
        for (int j = 0; j < n; j += (step << 1))
            for (int k = j; k < j + step; k++)
                arr[k] = (1LL * arr[k] + mod + 1LL * arr[k + step] * opt) % mod;
}

void fwt_xor(int *arr, int opt)
{
    for (int step = 1; step < n; step <<= 1)
        for (int j = 0; j < n; j += (step << 1))
            for (int k = j; k < j + step; k++)
            {
                int A = arr[k], B = arr[k + step];
                arr[k] = (1LL * A + B) % mod, arr[k + step] = (1LL * A + mod - B) % mod;
                if (opt == -1)
                    arr[k] = 1LL * arr[k] * inv2 % mod, arr[k + step] = 1LL * arr[k + step] * inv2 % mod;
            }
}

int main()
{
    scanf("%d", &n), n = 1 << n;
    for (int i = 0; i < n; i++)
        scanf("%d", &Ai[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &Bi[i]);

    memcpy(A, Ai, sizeof(A)), memcpy(B, Bi, sizeof(B));
    fwt_or(A, 1), fwt_or(B, 1);
    for (int i = 0; i < n; i++)
        C[i] = 1LL * A[i] * B[i] % mod;
    fwt_or(C, -1);
    for (int i = 0; i < n; i++)
        printf("%d ", C[i]);
    puts("");

    memcpy(A, Ai, sizeof(A)), memcpy(B, Bi, sizeof(B));
    fwt_and(A, 1), fwt_and(B, 1);
    for (int i = 0; i < n; i++)
        C[i] = 1LL * A[i] * B[i] % mod;
    fwt_and(C, -1);
    for (int i = 0; i < n; i++)
        printf("%d ", C[i]);
    puts("");

    memcpy(A, Ai, sizeof(A)), memcpy(B, Bi, sizeof(B));
    fwt_xor(A, 1), fwt_xor(B, 1);
    for (int i = 0; i < n; i++)
        C[i] = 1LL * A[i] * B[i] % mod;
    fwt_xor(C, -1);
    for (int i = 0; i < n; i++)
        printf("%d ", C[i]);
    puts("");
    return 0;
}

应用

CF662C Binary Table

发现\(n\)非常的小，所以我们可以考虑把每一列压起来，然后统计相同列数的个数。如果我们枚举行的反转情况\(S\)（第一位为\(1\)代表第一行反转），然后把操作生效，再扫一遍对每一列进行讨论就可以得到局部最优解，再合成到全剧最优解。这样时间复杂度很高，但是我们可以看到潜在的优化空间。我们可以考虑用数学的方式归纳出来：

\[ \sum_{S = 0}^{2^n – 1} \sum_{x \text{xor} y = S} cnt[x] \cdot best[y] \]

其中，我们把原来为\(x\)的列变成\(y\)，\(y\)的贡献自然是\(\min\{ \text{0的个数}, \text{1的个数} \}\)。

// CF662C.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 22, MAX_M = 1e5 + 200;

int n, m;
ll ai[1 << MAX_N], bi[1 << MAX_N], stats[MAX_M], poly_siz;

void fwt_xor(ll *arr, int opt)
{
    for (int step = 1; step < poly_siz; step <<= 1)
        for (int j = 0; j < poly_siz; j += (step << 1))
            for (int k = j; k < j + step; k++)
            {
                ll A = arr[k], B = arr[k + step];
                arr[k] = A + B, arr[k + step] = A - B;
                if (opt == -1)
                    arr[k] >>= 1, arr[k + step] >>= 1;
            }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1, val; j <= m; j++)
            scanf("%1d", &val), stats[j] |= (val << (i - 1));
    for (int i = 1; i <= m; i++)
        ai[stats[i]]++;
    for (int i = 0; i < (1 << n); i++)
        bi[i] = min(__builtin_popcount(i), n - __builtin_popcount(i));
    poly_siz = 1LL << n;
    fwt_xor(ai, 1), fwt_xor(bi, 1);
    for (int i = 0; i < poly_siz; i++)
        ai[i] *= bi[i];
    fwt_xor(ai, -1);
    ll ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; i < poly_siz; i++)
        ans = min(ans, ai[i]);
    printf("%lld\n", ans);
    return 0;
}

LOJ 152 子集卷积

子集卷积就是：

\[ \sum_{S \subset U} f_S g_{U – S} \]

现在题目要求我们对于不同的\(U\)进行求解。我们可以考虑给\(f\)和\(g\)按位为\(1\)的个数进行分类，变成\(\{f_b\}\)和\(\{g_b\}\)，再按位个数对\(n\)个多项式做 FWT_OR，然后就可以得到他们的子集展开。我们只需要枚举全集大小\(|U|\)和一个子集的大小\(|S|\)，再把展开后的进行相乘存入\(|U|\)的答案中即可。输出答案要注意从相应个数的多项式中提取。

#pragma GCC optimize(2)
// LOJ152.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = (1 << 22) + 2000, mod = 1e9 + 9;

int n, fi[22][MAX_N], gi[22][MAX_N], poly_siz, cnt[MAX_N], ans[22][MAX_N], gans[MAX_N];

inline char nc()
{
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

inline void fwt_or(int *arr, int opt)
{
    for (int step = 1; step < poly_siz; step <<= 1)
        for (int j = 0; j < poly_siz; j += (step << 1))
            for (int k = j; k < j + step; k++)
                arr[k + step] = (1LL * arr[k + step] + mod + 1LL * opt * arr[k]) % mod;
}

int main()
{
    n = read(), poly_siz = (1 << n);
    for (int i = 0; i <= poly_siz; i++)
        cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 0; i < poly_siz; i++)
        fi[cnt[i]][i] += read();
    for (int i = 0; i < poly_siz; i++)
        gi[cnt[i]][i] += read();
    for (int i = 0; i <= n; i++)
        fwt_or(fi[i], 1), fwt_or(gi[i], 1);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= i; j++)
            for (int k = 0; k < poly_siz; k++)
                ans[i][k] = (1LL * ans[i][k] + 1LL * fi[i - j][k] * gi[j][k] % mod) % mod;
    for (int i = 0; i <= n; i++)
        fwt_or(ans[i], -1);
    for (int i = 0; i < poly_siz; i++)
        printf("%d ", ans[cnt[i]][i]);
    puts("");
    return 0;
}