CF1336E1 Chiori and Doll Picking (easy version) (FWT，线性基，折半搜索)

发表于 | 阅读数

给$n$个数字($<2{m}$),求$2^n$取法，异或起来。询问$ans[0..m]=[popcount()=m]$，$m\leq 35,n\leq 2\times 2\times10^5$
$Sooke$牛逼啊。

  • 可以用线性基知道能表示出哪些数字。显然枚举$2^m$，不可能。

考虑$m=35$，考虑折半搜索。

找出前${\frac{m}{2}}$位,可以表达出来的数字$f1[i]$。

然后再找出后${\frac{m}{2}}$位,可以表达出来的数字$f2[cnt[i]][i]$。$cnt[i]$为$i$中二进制1的个数。

  • 由于第一组后$m/2$为$0$。不影响后${\frac{m}{2}}$位的个数。
  • 对两组的前$m/2$位$FWT$,$ans[i+j]+=[cnt[FWT(f2[j],f1)]=i]$

最后由于线性基的性质，$\times 2^{n-size}$

代码 
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1 << 20;
const int mod = 998244353;
const int MAXL = 35;
class LinearBase
{
public:
    ll p[MAXL];
    int pos[MAXL];
    void insert(ll x)
    {

        for (int i = MAXL - 1; i >= 0; i--)
        {
            if (x & (1ll << i))
            {
                if (!p[i])
                {
                    p[i] = x;

                    break;
                }

                x ^= p[i];
            }
        }
    }
    int size()
    {
        int res = 0;
        for (int i = 0; i < MAXL; i++)
            if (p[i])
                res++;
        return res;
    }
    int find(ll x)
    {
        for (int i = MAXL - 1; i >= 0; i--)
        {
            if (x & (1ll << i))
            {
                x ^= p[i];
            }
            if (x == 0)
                return 1;
        }
        return 0;
    }

} lb;

int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        x >>= 1;
        a = 1ll * a * a % mo;
    }
    return res;
}
int inc(int x, int y, int mo)
{
    if (y < 0)
        y += mo;
    if (x + y >= mo)
        x -= mo;
    return x + y;
}
int Inv2;
void FWT(int *A, int n, int op, int t) //t=1 or t=2 and t=3 xor
{
    for (int i = 2; i <= n; i <<= 1)
    {
        for (int j = 0, mid = i >> 1; j < n; j += i)
            for (int k = 0; k < mid; k++)
            {

                if (t == 1)
                    A[j + mid + k] = inc(A[j + mid + k], A[j + k] * op, mod);
                else if (t == 2)
                    A[j + k] = inc(A[j + k], A[j + mid + k] * op, mod);
                else if (t == 3)
                {
                    int x = A[j + k], y = A[j + mid + k];
                    if (op == 1)
                        A[j + k] = (x + y) % mod, A[j + mid + k] = (x - y + mod) % mod;
                    else
                        A[j + k] = 1ll * Inv2 * (x + y) % mod, A[j + mid + k] = 1ll * Inv2 * (x - y + mod) % mod;
                }
            }
    }
}
void FWTX(int *A, int *B, int n, int t)
{

    Inv2 = qpow(2, mod - 2, mod);
    FWT(A, n, 1, t), FWT(B, n, 1, t);

    for (int i = 0; i < n; ++i)
        A[i] = 1ll * A[i] * B[i] % mod;
    FWT(A, n, -1, t);
}
int n, m;
int cnt[N], mid;
int ans[N];
int f[20][N], c[N], g[N];
void dfs(int x, ll k)
{
    if (x == m)
    {

        f[cnt[(k) >> mid]][k & ((1 << mid) - 1)]++;
        return;
    }
    dfs(x + 1, k);
    if (lb.p[x])
        dfs(x + 1, lb.p[x] ^ k);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < N; i++)
        cnt[i] = __builtin_popcount(i);
    for (int i = 1; i <= n; i++)
    {
        ll x;
        scanf("%lld", &x);
        lb.insert(x);
    }
    mid = (1 + m) >> 1;

    for (int i = 0; i < (1 << mid); i++)
        c[i] = lb.find(i);

    dfs(mid, 0);
    for (int i = 0; i <= m - mid; i++)
    {
        for (int j = 0; j < (1 << mid); j++)
            g[j] = c[j];

        FWTX(f[i], g, 1 << mid, 3);

        for (int j = 0; j < (1 << mid); j++)
            ans[i + cnt[j]] += f[i][j], ans[i + cnt[j]] %= mod;
    }
    int p = qpow(2, n - lb.size(), mod);
    for (int j = 0; j <= m; j++)
        ans[j] = 1ll * ans[j] * p % mod;
    for (int j = 0; j <= m; j++)
        printf("%d ", ans[j]);
}