3347. 多项式展开 (3)

单点时限: 3.0 sec

内存限制: 256 MB

$F_n(x)$ 是多项式,递归定义如下:

  • $F_0(x) = 1$;
  • $F_1(x) = x$;
  • $F_n(x) = A(x) \cdot F_{n-1}(x) + B(x) \cdot F_{n-2}(x), \forall n \geq 2$。

其中 $A(x), B(x)$ 分别为 $n,m$ 项多项式。

现在给出 $A(x), B(x)$,求 $F_k(x)$。注意到 $F_k(x)$ 项数可能非常多,这里只要求输出次数不超过 $t$ 的项。

也就是说,如果 $F_k(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_t x^t + \cdots$,你只需要输出 $a_0, a_1, \ldots, a_t$ 即可。如果该项不存在,就记为 $0$。结果仍然可能很大,模 $998~244~353$。

输入格式

第一行一个整数 $n$ $(0 \leq n \leq 4~000)$。

第二行 $n+1$ 个整数用空格隔开 $a_0, a_1, \ldots, a_n$ $(0 \leq a_i \leq 10^8)$,表示多项式 $A(x) = \sum_{i=0}^n a_i x^i$。

第三行一个整数 $m$ $(0 \leq m \leq 4~000)$。

第四行 $m+1$ 个整数,同理表示 $B(x)$。

最后一行两个整数分别为 $k,t$ $(1 \leq k \leq 10^9, 0 \leq t \leq 4~000)$。

输出格式

按照题目要求输出 $t+1$ 个整数,格式任意。

样例

Input
1
0 2
0
5
2 2
Output
5 0 2
Input
0
1
0
1
2 2
Output
1 1 0
Input
0
1
0
1
1 0
Output
0

2 人解决,3 人已尝试。

2 份提交通过,共有 6 份提交。

8.8 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,9 月前.

最后提交: 2 年,9 月前.

来源: N/A

题目标签