[Problem proposal] Polynomial Composite Set Power Series (Transposed)

[hos-lyric]

Problem name: Polynomial Composite Set Power Series (Transposed)

Problem

• 非負整数 $M$
• 長さ $2 ^ N$ の列 $c$
• $N$ 元集合上の集合冪級数 $s$

が与えられたとき， $k = 0, 1, \ldots, M-1$ に対して $\sum_i c_i (s^k)_i$ を計算する ($(s^k)_i$ は $s$ の $k$ 乗の $i$ 項目) mod 998244353

Constraint

• $0 \leq M \leq 10^5$
• $0 \leq N \leq 20$

Reference

• https://codeforces.com/blog/entry/92183

• 944

• 951

• https://atcoder.jp/contests/xmascon22/tasks/xmascon22_f (解説ブログをさぼっていて，すみません……)

Input

$M$ $N$ $c_0$ $c1$ $\cdots$ $c{2^N-1}$ $s_0$ $s1$ $\cdots$ $s{2^N-1}$

Note

944 の転置です

意見募集

• タイトルは内容を直接表してもいいかもしれないんですが，「合成の転置」よりわかりやすい名前が思いつきませんでした
• $M = N$ かつ $s_0 = 0$ でもいいと思いますが，とりあえず #944 と対応させておきました
• 内積みたいな感じではなく， $c$ も集合冪級数にして $c s^k$ の全体集合における係数を求めよという形もあり得て (つまり $c$ を reverse)，どっちがいいかよくわかりませんでした
• 変数名 (#951 と対応させるなら in: $c, b$, out: $a$ とか？)
• 入力の順番 (どっちが先か)

[maspypy]

全体集合における係数

transpose なら $\sum c_i(s^k)_i$ の方がよいと思います。

変数名 in: c, b

これがまあ妥当かなと思います（双対基底に関する成分なのでちょっと嫌だという気持ちは分かるが、良い代案は特に持っていないです）

[maspypy]

作業者募集で。

[maspypy]

問題名について https://arxiv.org/pdf/2404.05177.pdf ここでは、Power Projection という呼称が使われている