首页 题解

# P4717 【模板】快速莫比乌斯 / 沃尔什变换 (FMT/FWT)

先放一个模板后面写题直接复制就可以了。

FWTFWT 原理就不解释了，大家自己去看题解吧 QwQ

这里直接放代码。

CodeCode

#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1 << 18;
const int mod = 998244353;
int n;
int A[N], B[N], a[N], b[N];
int f[N];
inline int add(int x) {return x >= mod ? x % mod : x;}
inline int sub(int x) {return x < 0 ? x % mod + mod : x;}
inline int calc(ll x) {return (x % mod + mod) % mod;}
inline void init(){
    memcpy(a, A, sizeof(A)), memcpy(b, B, sizeof(B));
}
inline void OR(int f[], int typ){
    for(int k = 1; k < n; k <<= 1)
        for(int i = 0; i < n; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j + k] = calc(f[i + j + k] + f[i + j] * typ);
}
inline void AND(int f[], int typ){
    for(int k = 1; k < n; k <<= 1)
        for(int i = 0; i < n; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j] = calc(f[i + j] + f[i + j + k] * typ);
}
inline void XOR(int f[], int typ){
    for(int k = 1; k < n; k <<= 1)
        for(int i = 0; i < n; i += (k << 1))
            for(int j = 0; j < k; ++j){
                f[i + j] = add(f[i + j] + f[i + j + k]);
                f[i + j + k] = sub(f[i + j] - f[i + j + k] - f[i + j + k]);
                f[i + j] = calc(1ll * f[i + j] * typ), f[i + j + k] = calc(1ll * f[i + j + k] * typ);
            }
}
inline void fwt_OR(){
    init(), OR(a, 1), OR(b, 1);
    for(int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % mod;
    OR(a, -1);
    for(int i = 0; i < n; ++i) write(a[i]), putchar(' ');
    puts("");
}
inline void fwt_AND(){
    init(), AND(a, 1), AND(b, 1);
    for(int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % mod;
    AND(a, -1);
    for(int i = 0; i < n; ++i) write(a[i]), putchar(' ');
    puts("");
}
inline void fwt_XOR(){
    init(), XOR(a, 1), XOR(b, 1);
    for(int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % mod;
    XOR(a, 499122177);
    for(int i = 0; i < n; ++i) write(a[i]), putchar(' ');
    puts("");
}
signed main(){
    n = 1 << read();
    for(int i = 0; i < n; ++i) A[i] = read();
    for(int i = 0; i < n; ++i) B[i] = read();
    fwt_OR(), fwt_AND(), fwt_XOR();
    return 0;
}
# P6097【模板】子集卷积
FWTFWT 经典应用，也有许多题目使用到了【子集卷积】这个做法。
我们把两个限制分开来考虑。
第一个 i&j=0i \& j = 0 比较简单，直接使用 FWTFWT 计算子集并卷积即可。
那么 i∣j=ki | j = k 如何处理呢？同时考虑这两个限制，相当于是 ∣i∣+∣j∣=∣i∪j∣|i| + |j| = |i \cup j|，所以我们再开一维数组记录 ii 中 1 的个数，fi,sf_{i, s} 中 ii 表示 ss 中 1 的个数，那么有：
\begin{equation} f_{i, j}= \begin{cases} 0 & |j| \neq i\\ a_j & |j| = i \end{cases} \end{equation} \begin{equation} g_{i, j}= \begin{cases} 0 & |j| \neq i\\ b_j & |j| = i \end{cases} \end{equation}
hih_i 即为 fkf_k 和 gi−kg_{i - k} 的并卷积。
CodeCode
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = (1 << 20) + 10;
const int mod = 1e9 + 9;
int n, m;
int a[25][N], b[25][N], f[25][N];
inline int calc(int x) {return __builtin_popcount(x);}
inline int add(int x) {return (x % mod + mod) % mod;}
inline void fwt_or(int f[], int typ){
    for(int k = 1; k < n; k <<= 1)
        for(int i = 0; i < n; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j + k] = add(f[i + j + k] + 1ll * f[i + j] * typ);
}
signed main(){
    n = 1 << (m = read());
    for(int i = 0; i < n; ++i) a[calc(i)][i] = read();
    for(int i = 0; i < n; ++i) b[calc(i)][i] = read();
    for(int i = 0; i <= m; ++i) fwt_or(a[i], 1), fwt_or(b[i], 1);
    for(int i = 0; i <= m; ++i)
        for(int j = 0; j <= i; ++j)
            for(int k = 0; k < n; ++k)
                f[i][k] = add(f[i][k] + 1ll * a[j][k] * b[i - j][k] % mod);
    for(int i = 0; i <= m; ++i) fwt_or(f[i], -1);
    for(int i = 0; i < n; ++i) write(f[calc(i)][i]), putchar(' ');
    return 0;
}
# SP2829 TLE - Time Limit Exceeded
观察到 aia_i 的取值范围为 0∼2m0 \sim 2^m，mm 也很小，显然要使用状压 dp\text{dp}。
设 dpi,jdp_{i, j} 表示第 ii 位填 jj 的方案数，那么有：
\begin{equation} dp_{i, j}= \begin{cases} 0& j\ \%\ c_i\ \neq 0\\ \sum\limits_{k \& j = 0}dp_{i - 1, j} & j\ \%\ c_i\ = 0 \end{cases} \end{equation}
不难发现，kk 的所有取值就是 j⊕(m−1)j \oplus (m - 1) 的所有子集，所以我们求一遍子集前缀和就可以转移了。
可以使用 FWT_ORFWT\_OR 来快速计算。
CodeCode
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 55;
const int mod = 1e9;
int T, n, m;
int a[N], f[N][(1 << 15) + 10];
inline int add(int x) {return x >= mod ? x - mod : x;}
inline void fwt_OR(int f[]){
    for(int k = 1; k < m; k <<= 1)
        for(int i = 0; i < m; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j + k] = add(f[i + j + k] + f[i + j]);
}
signed main(){
    T = read();
    while(T--){
        memset(f, 0, sizeof(f));
        n = read(), m = 1 << read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        for(int i = 1; i < m; ++i) f[1][i] = (i % a[1]) ? 1 : 0;
        fwt_OR(f[1]);
        for(int i = 2; i <= n; ++i){
            for(int j = 1; j < m; ++j)
                if(j % a[i]) f[i][j] += f[i - 1][j ^ (m - 1)];
            fwt_OR(f[i]);
        }
        write(f[n][m - 1]), puts("");
    }
    return 0;
}
# CF914G Sum the Fibonacci
看到题目中有许多条件，但是不要慌，我们把这些条件一个一个拆开来看。
题目要求对满足 (sa∣sb)&sc&(sd⊕se)=2p(s_a | s_b) \& s_c \& (s_d \oplus s_e) = 2^p，且 sa&sb=0s_a \& s_b = 0 的五元组求 ∑f(sa∣sb)×f(sc)×f(sd⊕se)\sum f(s_a | s_b) \times f(s_c) \times f(s_d \oplus s_e)（fif_i 为斐波那契数列）。
我们令 i=sa∣sb,j=sc,k=sd⊕sei = s_a | s_b,\ j = s_c,\ k = s_d \oplus s_e，那么 i,j,ki, j, k 要满足 i&j&k=2pi \& j \& k = 2^p，我们求的就是 ∑f(i)×f(j)×f(k)\sum f(i) \times f(j) \times f(k)。
即：
∑p∑i&j&k=2pfi×(∑sa∣sb=i,sa&sb=01)×fj×(∑sc=j1)×fk×(∑sd⊕se=k1)\sum_{p}\sum_{i \& j \& k = 2^p} f_i \times (\sum_{s_a | s_b = i, s_a \& s_b = 0} 1) \times f_j \times (\sum_{s_c = j} 1) \times f_k \times (\sum_{s_d \oplus s_e = k} 1)
第一个 sa,sbs_a, s_b 的求和就是一个子集卷积，中间的 sc=js_c = j 就是个桶，最后面的 sd⊕ses_d \oplus s_e 的求和就是一个异或卷积。
所以直接把上面几道题的板子复制过来改改就过了。
那么这里还是贴一下代码。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1 << 17;
const int mod = 1e9 + 7;
const int inv2 = 500000004;
int n, ans;
int a[N], b[N], c[N];
int f[20][N], h[N], g[N], fib[N], cnt[N];
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int sub(int x) {return x < 0 ? x + mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline int calc(int x) {return (x % mod + mod) % mod;}
inline void init(){
    fib[1] = cnt[1] = 1;
    for(int i = 2; i < N; ++i)
        fib[i] = add(fib[i - 1] + fib[i - 2]), cnt[i] = cnt[i >> 1] + (i & 1);
}
inline void fwt_or(int *f, int typ){
    for(int k = 1; k < N; k <<= 1)
        for(int i = 0; i < N; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j + k] = calc(f[i + j + k] + 1ll * typ * f[i + j]);
}
inline void fwt_and(int *f, int typ){
    for(int k = 1; k < N; k <<= 1)
        for(int i = 0; i < N; i += (k << 1))
            for(int j = 0; j < k; ++j)
                f[i + j] = calc(f[i + j] + 1ll * typ * f[i + j + k]);
}
inline void fwt_xor(int *f, int typ){
    for(int k = 1; k < N; k <<= 1)
        for(int i = 0; i < N; i += (k << 1))
            for(int j = 0; j < k; ++j){
                int x = f[i + j], y = f[i + j + k];
                f[i + j] = mul(typ, add(x + y)), f[i + j + k] = mul(typ, sub(x - y));
            }
}
signed main(){
    n = read(), init();
    for(int i = 1, x; i <= n; ++i) x = read(), a[x]++, b[x]++, c[x]++;
    for(int i = 0; i < N; ++i) f[cnt[i]][i] = a[i], a[i] = 0;
    for(int i = 0; i < 18; ++i) fwt_or(f[i], 1);
    for(int i = 0; i < 18; ++i){
        memset(h, 0, sizeof(h));
        for(int j = 0; j <= i; ++j)
            for(int k = 0; k < N; ++k)
                h[k] = add(h[k] + 1ll * f[j][k] * f[i - j][k] % mod);
        fwt_or(h, -1);
        for(int j = 0; j < N; ++j)
            if(i == cnt[j]) a[j] = add(a[j] + h[j]);
    }
    fwt_xor(c, 1);
    for(int i = 0; i < N; ++i) c[i] = mul(c[i], c[i]);
    fwt_xor(c, inv2);
    for(int i = 0; i < N; ++i) a[i] = mul(a[i], fib[i]), b[i] = mul(b[i], fib[i]), c[i] = mul(c[i], fib[i]);
    fwt_and(a, 1), fwt_and(b, 1), fwt_and(c, 1);
    for(int i = 0; i < N; ++i) g[i] = mul(a[i], mul(b[i], c[i]));
    fwt_and(g, -1);
    for(int i = 1; i < N; i <<= 1) ans = add(ans + g[i]);
    write(ans), puts("");
    return 0;
}
# CF662C Binary Table
非常巧妙的题。
首先观察到 n≤20n \leq 20 但是 m≤105m \leq 10^5 是什么鬼？
先想一个比较显然的暴力，我们 2n2^n 枚举每一行是否翻转，然后每一列的状态就都是已知的了，O(m)O(m) 枚举所有的列，答案加上当前列 0/10/1 出现次数较小值即可，时间复杂度 O(m2n)O(m2^n)。
那么显然这个 mm 实在是太大了，考虑如何去掉 mm。
一共有 mm 种列状态，每种状态都是 0∼2n−10 \sim 2^n - 1 里的一种，我们记 aia_i 表示状态 ii 出现的次数，bib_i 表示状态 ii 中 0/10/1 出现次数的较小值。
假设当前枚举的行状态为 stasta，那么答案就是：
ans=∑i=02n−1ai×bi⊕staans = \sum_{i = 0}^{2^n - 1} a_i \times b_{i \oplus sta}
状态为 ii 的有 aia_i 列，翻转之后每一列上 1 的个数都为 bi⊕stab_{i \oplus sta}。
设 fif_i 表示状态为 ii 时的答案，那么有：
fk=∑i⊕j=kai×bjf_k = \sum_{i \oplus j = k} a_i \times b_j
所以求一下 aia_i 和 bib_i 的异或卷积，然后统计答案即可。
CodeCode
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = (1 << 20) + 10;
const int M = 1e5 + 10;
const int inf = 1e18;
int n, m, lim, ans = inf;
char s[M];
int f[N], g[M], a[N], b[N];
inline int calc(int x) {
    int cnt = __builtin_popcount(x);
    return min(cnt, n - cnt);
}
inline void fwt_xor(int f[], int typ){
    for(int k = 1; k < lim; k <<= 1)
        for(int i = 0; i < lim; i += (k << 1))
            for(int j = 0; j < k; ++j){
                int x = f[i + j], y = f[i + j + k];
                if(typ == 1) f[i + j] = x + y, f[i + j + k] = x - y;
                else f[i + j] = (x + y) >> 1, f[i + j + k] = (x - y) >> 1;
            }
}
signed main(){
    n = read(), m = read(), lim = 1 << n;
    for(int i = 0; i < n; ++i){
        scanf("%s", s);
        for(int j = 0; j < m; ++j)
            if(s[j] == '1') g[j] |= (1 << i);
    }
    for(int i = 0; i < m; ++i) a[g[i]]++;
    for(int i = 0; i < lim; ++i) b[i] = calc(i);
    fwt_xor(a, 1), fwt_xor(b, 1);
    for(int i = 0; i < lim; ++i) f[i] = a[i] * b[i];
    fwt_xor(f, -1);
    for(int i = 0; i < lim; ++i) ans = min(ans, f[i]);
    write(ans), puts("");
    return 0;
}
# CF850E Random Elections
这是我见过的最巧妙的 FWTFWT 题目。
题意就不解释了。
显然一轮中赢两次的玩家之后一个，所以计算一个人获胜的次数乘 3 即可。
考虑一个人如何才能获胜。
对于两场比赛 A−B,C−AA - B, C - A（题目要求），AA 的的票状态分别为 S1,S2S_1, S_2，假设它们第 ii 位的情况为 (x,y)(x, y)（ x,y=0/1x, y = 0/1），那么有 4 中情况：
  • (x,y)=(0,0)⇒CAB,CBA(x, y) = (0, 0) \Rightarrow CAB, CBA
  • (x,y)=(1,0)⇒CAB(x, y) = (1, 0) \Rightarrow CAB
  • (x,y)=(0,1)⇒BAC(x, y) = (0, 1) \Rightarrow BAC
  • (x,y)=(1,1)⇒ABC,ACB(x, y) = (1, 1) \Rightarrow ABC, ACB
后面的字母串表示这个人可能的投票顺序。
根据乘法原理，(1,0)(1, 0) 和 (0,1)(0, 1) 都是没有贡献的（均为乘 1），(0,0)(0, 0) 和 (1,1)(1, 1) 均有 2 的贡献。
所以设 S=S1⊕S2S = S_1 \oplus S_2，cntcnt 为 SS 中 0 的个数，那么方案数就是 2cnt2^{cnt}。
给 fsf_s 赋好初值以后，不难发现这东西就是一个 ff 自己和自己的异或卷积！
于是这题就愉快的解决了。
CodeCode
#include <bits/stdc++.h>
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = (1 << 20) + 10;
const int mod = 1e9 + 7;
const int inv2 = 500000004;
int n, lim, ans;
char s[N];
int f[N], g[N];
inline int add(int x) {return x >= mod ? x - mod : x;}
inline int mul(int x, int y) {return 1ll * x * y % mod;}
inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}
inline void fwt_xor(int f[], int typ){
    for(int k = 1; k < lim; k <<= 1)
        for(int i = 0; i < lim; i += (k << 1))
            for(int j = 0; j < k; ++j){
                int x = f[i + j], y = f[i + j + k];
                f[i + j] = mul(x + y, typ), f[i + j + k] = mul(x - y, typ);
            }
}
signed main(){
    n = read(), lim = 1 << n;
    scanf("%s", s);
    for(int i = 0; i < lim; ++i) f[i] = s[i] - '0';
    fwt_xor(f, 1);
    for(int i = 0; i < lim; ++i) f[i] = mul(f[i], f[i]);
    fwt_xor(f, inv2);
    for(int i = 0; i < lim; ++i)
        ans = add(ans + mul(f[i], qpow(2, n - __builtin_popcount(i))));
    write(mul(3, ans)), puts("");
    return 0;
}
 阅读次数  次