No.623 fudan no modulus to tigau
タグ : / 解いたユーザー数 80
作問者 :
n_vip
/ テスター :
夕叢霧香(ゆうむらきりか)
問題文
多項式 \(f(x)\) があります。\(q\) 個の値 \(x_1, ... , x_q\) に対して、 \(f(x_1) , ... , f(x_q)\) を求めて下さい。
多項式 \(f(x)\) は、以下のように定義される多項式の列 \(f_0(x), ..., f_n(x)\) の末尾の多項式 \(f_n(x)\) として定義します。
- \(f_0(x) = 1\)
- \(f_1(x) = x\)
- \(i\geq 2\) に対して、
- \(t_i = 1\) のとき、\(f_i(x) = f_{a_i}(x) + f_{b_i}(x)\)
- \(t_i = 2\) のとき、\(f_i(x) = a_i \times f_{b_i}(x)\)
- \(t_i = 3\) のとき、\(f_i(x) = f_{a_i}(x) \times f_{b_i}(x)\)
答えは非常に大きくなることがあるので、\(998244353\) で割ったあまりを求めて下さい。
入力
$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$
制約
- \(2 \leq n \leq 50\)
- \(1 \leq q \leq 50\)
- \(0 \leq a_i, b_i < i\)
- \(0 \leq x_i < 998244353\)
出力
\(q\) 行出力して下さい。 \(i\) 行目には、 \(f(x_i)\) を \(998244353\) で割ったあまりを出力して下さい。
サンプル
サンプル1
入力
6 1 1 1 1 0 2 3 1 3 3 3 4 2 5 5 1 3
出力
735
多項式はそれぞれ次のようになります。
\(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\)
\(f_6(x)\) に \(3\) を代入すると \(735\) です。
サンプル2
入力
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
出力
1 16 65535 951843729
多項式はそれぞれ次のようになります。
\(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もしくは右上の雲マークをクリックしてアカウントを作成してください。