mechanicalpenciI さんの公式解説（以下、公式解説）の亜種です。

公式解説同様に \(C\) を定義します。この \(C\) を \(\left ( \mathbb Z / 2 \mathbb Z \right ) ^ { 16 }\) 上の群環 \(R = \mathbb { F } _ { 998244353 } [ \left ( \mathbb Z / 2 \mathbb Z \right ) ^ { 16 } ]\)（xor 畳み込みの環）の要素とみなし、以下これらの積を書けば xor 畳み込みのことであるとしましょう。求めたいものは \(\sum _ { i = 0 } ^ { N - 1 } C ^ i\) （本当はこれの \(C\) 倍ですがそれは後でかければよいです。）です。そこで \(R\) の点列 \(X _ i, Y _ i (i = 0, 1, \dots )\) を次のように定めます。

\[ X _ i = C ^ i, \quad Y _ i = \sum _ { j = 0 } ^ { i - 1 } C ^ j \]

このとき

\[ X _ { i + j } = X _ i X _ j, \quad Y _ { i + j } = Y _ i + X _ i Y _ j \]

が成り立ちますから、これによりダブリングで高速に \(Y _ N = \sum _ { i = 0 } ^ { N - 1 } C ^ i\) を計算することができます。最悪時間計算量は、\(m _ A = \max A _ i\) として、\(O ( m _ A \lg m _ A \lg N )\) となります。高速アダマール変換をする回数は、\(N\) の桁数と popcount の合計の \(4\) 倍回（最大で、公式解説の \(64\) 倍回くらい）です。けっこうギリギリですが通りました。

解答例 (Rust): https://atcoder.jp/contests/abc212/submissions/24699220