首页 题解

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

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

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

这里直接放代码。

CodeCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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 的个数，那么有：

fi,j={0∣j∣≠iaj∣j∣=i\begin{equation} f_{i, j}= \begin{cases} 0 & |j| \neq i\\ a_j & |j| = i \end{cases} \end{equation}

gi,j={0∣j∣≠ibj∣j∣=i\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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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 的方案数，那么有：

dpi,j={0j % ci ≠0∑k&j=0dpi−1,jj % ci =0\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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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 的求和就是一个异或卷积。

所以直接把上面几道题的板子复制过来改改就过了。

那么这里还是贴一下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}

阅读次数 次