题目 30217

集合幂级数 exp

查看题解 ↗GitHub ↗如何评测
题号
30217
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - exp_of_set_power_series

【题目描述】

给定一个 NN 元多项式

s(x0,x1,…,xN−1)=∑i=02N−1bi∏k=0N−1xkik∈F998244353[x0,x1,…,xN−1]s(x _ 0, x _ 1, \dots, x _ {N - 1}) = \sum _ {i = 0} ^ {2 ^ N - 1} b _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \in \mathbb{F} _ {998244353} \lbrack x _ 0, x _ 1, \dots, x _ {N - 1} \rbrack

其中,iki_k 表示将 ii 表示为二进制数时第 2k2 ^ k 位上的数字。

请输出 c0,c1,…,c2N−1c _ 0, c _ 1, \dots, c _ {2 ^ N - 1}(0≤ci<9982443530 \leq c _ i < 998244353),使其满足

∑m=0Ns(x0,x1,…,xN−1)mm!≡∑i=02N−1ci∏k=0N−1xkik(mod(x02,x12,…,xN−12))\sum _ {m = 0} ^ N \frac{s(x _ 0, x _ 1, \dots, x _ {N - 1})^m}{m!} \equiv \sum _ {i = 0} ^ {2 ^ N - 1} c _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \pmod{(x _ 0 ^ 2, x _ 1 ^ 2, \dots, x _ {N - 1} ^ 2)}

。

【输入】

输入格式如下:

文本
$N$
$b_0$ $b_1$ $\cdots$ $b_{2^N-1}$

【输出】

输出格式如下:

文本
$c_0$ $c_1$ $\cdots$ $c_{2^N-1}$

【输入样例】

文本
3
0 6 7 8 9 10 11 12

【输出样例】

文本
1 6 7 50 9 64 74 598

【数据范围】

  • 0≤N≤200 \leq N \leq 20
  • 0≤bi<9982443530 \leq b_i < 998244353
  • b0=0b_0 = 0

【来源】

Library Checker(yosupo06) exp_of_set_power_series

数据下载

题目 30217 的公开数据

正在读取文件列表…

常用命令

题目 30217 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。