kanade’s convolution

已知$A$和$B$数列，且

$$C_{k} = sum_{i and j = k} A_{i xor j} times B_{i or j}.$$

计算 $sum_{i=0}^{ {2}^{m} - 1} C_{i} times {1526}^{i}$ $mod$ $998244353.$

设$i$ $or$ $j = x$,$i$ $xor$ $j = y$.那么$i$ $and$ $j = x$ $xor$ $y$.且要求$x$ $and$ $y = y$.

$$C_{k} = sum_{x} sum_{y} [x and y == y] times [x xor y == k] times B_{x} times A_{y} times {2}^{bit(y)}.$$ $$C_{k} = sum_{x xor y = k} [x and y == y] times B_{x} times A_{y} times {2}^{bit(y)}.$$ $$C_{k} = sum_{x xor y = k} [bit(x) - bit(y) == bit(k)] times B_{x} times A_{y} times {2}^{bit(y)}.$$

考虑新的函数$F(A, k)_{i}$表示$[bit(i)==k] times A_{i}$，$F(B, k)_{i}$同理。

则有$FWT[F(C, h)] = sum_{i=k}^{m} FWT[F(A, i-h)] * FWT[F(B, i) )].$

$$C_{k} = F(C, bit(k))_{k}.$$

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

using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "