No.623 fudan no modulus to tigau
タグ : / 解いたユーザー数 82
作問者 :
n_vip
/ テスター :
夕叢霧香(ゆうむらきりか)
Problem Statement
There is a polynomial \(f(x)\). For \(q\) values \(x_1, ... , x_q\), find \(f(x_1) , ... , f(x_q)\).
The polynomial \(f(x)\) is defined as the last polynomial \(f_n(x)\) of the sequence of polynomials \(f_0(x), ..., f_n(x)\) defined as follows.
- \(f_0(x) = 1\)
- \(f_1(x) = x\)
- For \(i\geq 2\),
- if \(t_i = 1\), then \(f_i(x) = f_{a_i}(x) + f_{b_i}(x)\)
- if \(t_i = 2\), then \(f_i(x) = a_i \times f_{b_i}(x)\)
- if \(t_i = 3\), then \(f_i(x) = f_{a_i}(x) \times f_{b_i}(x)\)
Since the answers can be very large, find them modulo \(998244353\).
Input
$n$ $t_2$ $a_2$ $b_2$ $t_3$ $a_3$ $b_3$ $\vdots$ $t_n$ $a_n$ $b_n$ $q$ $x_1$ $x_2$ $\dots$ $x_q$
Constraints
- \(2 \leq n \leq 50\)
- \(1 \leq q \leq 50\)
- \(0 \leq a_i, b_i < i\)
- \(0 \leq x_i < 998244353\)
Output
Print \(q\) lines. On the \(i\)-th line, print \(f(x_i)\) modulo \(998244353\).
Sample
Sample 1
Input
6 1 1 1 1 0 2 3 1 3 3 3 4 2 5 5 1 3
Output
735
The polynomials are as follows.
\(f_2(x) = 2x\)
\(f_3(x) = 1 + 2x\)
\(f_4(x) = x + 2x^2\)
\(f_5(x) = x + 4x^2 + 4x^3\)
\(f_6(x) = 5x + 20x^2 + 20x^3\)
Substituting \(3\) into \(f_6(x)\) gives \(735\).
Sample 2
Input
12 3 1 1 3 2 2 3 3 3 3 4 4 1 0 1 3 2 6 1 6 7 3 3 8 1 8 9 3 4 10 1 10 11 4 0 1 2 20171223
Output
1 16 65535 951843729
The polynomials are as follows.
\(f_2(x) = x^2\)
\(f_3(x) = x^4\)
\(f_4(x) = x^8\)
\(f_5(x) = x^{16}\)
\(f_6(x) = 1 + x\)
\(f_7(x) = x^2 + x^3\)
\(f_8(x) = 1 + x + x^2 + x^3\)
\(f_9(x) = x^4 + x^5 + x^6 + x^7\)
\(f_{10}(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7\)
\(f_{11}(x) = x^8 + x^9 + x^{10} + x^{11} + x^{12} + x^{13} + x^{14} + x^{15}\)
\(f_{12}(x) = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10} + x^{11} + x^{12} + x^{13} + x^{14} + x^{15}\)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。