题目 30218

集合幂级数 log

查看题解 ↗GitHub ↗如何评测
题号
30218
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - log_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−1 (0≤ci<998244353)c _ 0, c _ 1, \dots, c _ {2 ^ N - 1} ~ (0 \leq c _ i \lt 998244353):

log⁡(s(x0,x1,…,xN−1))≡∑i=02N−1ci∏k=0N−1xkik(mod(x02,x12,…,xN−12)).\log(s(x _ 0, x _ 1, \dots, x _ {N - 1})) \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)}.

换句话说,请输出 c0,c1,…,c2N−1 (0≤ci<998244353)c _ 0, c _ 1, \dots, c _ {2 ^ N - 1} ~ (0 \leq c _ i \lt 998244353),其中

t(x0,x1,…,xN−1)=∑i=02N−1ci∏k=0N−1xkik∈F998244353[x0,x1,…,xN−1]t(x _ 0, x _ 1, \dots, x _ {N - 1}) = \sum _ {i = 0} ^ {2 ^ N - 1} c _ i \prod _ {k = 0} ^ {N - 1} x _ k ^ {i _ k} \in \mathbb{F} _ {998244353} \lbrack x _ 0, x _ 1, \dots, x _ {N - 1} \rbrack
满足 c0=0c _ 0 = 0,且

s(x0,x1,…,xN−1)≡∑m=0Nt(x0,x1,…,xN−1)mm!(mod(x02,x12,…,xN−12)).s(x _ 0, x _ 1, \dots, x _ {N - 1}) \equiv \sum _ {m = 0} ^ N \frac{t(x _ 0, x _ 1, \dots, x _ {N - 1})^m}{m!} \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
1 6 7 50 9 64 74 598

【输出样例】

文本
0 6 7 8 9 10 11 12

【数据范围】

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

【来源】

Library Checker(yosupo06) log_of_set_power_series

数据下载

题目 30218 的公开数据

正在读取文件列表…

常用命令

题目 30218 的 ROJ 命令

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