QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 2048 MB Total points: 100 Hackable ✓
[+1]

# 1097. 多项式复合

Statistics

给定 F(x)=n1i=0fixiG(x)=n1i=0gixi,其中 g0=0

H(x) = F(G(x)) \pmod{x^{n}} 的各项系数,取模 998\,244\,353

输入格式

输入的第一行包含一个整数 N

接下来一行,包含 N 个整数 f_0, f_1, \cdots, f_{n-1}。保证对每个 i0 \leq f_i < 998\,244\,353

接下来一行,包含 N 个整数 g_0, g_1, \cdots, g_{n-1}。保证有 g_0 = 0,且对每个 i0 \leq g_i < 998\,244\,353

输出格式

输出一行,包含 N 个整数 h_0, h_1, \cdots, h_{n-1}

样例数据

样例输入

6
1 1 4 5 1 4
0 9 0 2 2 8

样例输出

1 9 324 3647 6707 238778

子任务

对于所有的数据,我们有 1 \leq N \leq 50\,000

子任务 N \leq
1 10
2 1\,000
3 2\,000
4 4\,000
5 7\,000
6 10\,000
7 15\,000
8 20\,000
9 30\,000
10 50\,000