問題一覧 > 通常問題

No.623 fudan no modulus to tigau

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : n_vipn_vip / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
2 ProblemId : 471 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-04 20:20:46

問題文


多項式 \(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もしくは右上の雲マークをクリックしてアカウントを作成してください。