問題一覧 > 通常問題

No.1891 Static Xor Range Composite Query

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : SSRSSSRS / テスター : noiminoimi
5 ProblemId : 7923 / 自分の提出
問題文最終更新日: 2022-04-04 17:58:10

問題文

長さ $N$ の一次関数の列 $f_0, f_1, \dots, f_{N-1}$ が与えられます。$f_i(x)=a_ix+b_i$ です。
$Q$ 個のクエリが与えられるので、処理してください。
$i$ 番目のクエリでは、整数 $l, r, p, x$ が与えられるので、$f_{(r-1) \oplus p}(f_{(r-2) \oplus p}(\dots f_{(l+1) \oplus p}(f_{l \oplus p}(x)) \dots )) \bmod 998244353$ を出力してください。
ただし、$\oplus$ はビット単位の排他的論理和を表します。

入力

$N\ Q$
$a_0 \ b_0$
$a_1 \ b_1$
$\vdots$
$a_{N-1} \ b_{N-1}$
$l_0 \ r_0 \ p_0 \ x_0$
$l_1 \ r_1 \ p_1 \ x_1$
$\vdots$
$l_{Q-1} \ r_{Q-1} \ p_{Q-1} \ x_{Q-1}$

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $N$ は $2$ べきである
  • $1 \leq N \leq 2^{18} = 262144$
  • $1 \leq a_i < 998244353 \ (0 \leq i < N)$
  • $0 \leq b_i < 998244353 \ (0 \leq i < N)$
  • $1 \leq Q \leq 2 \times 10^5$
  • $0 \leq l_i < r_i \leq N \ (0 \leq i < Q)$
  • $0 \leq p_i < N \ (0 \leq i < Q)$
  • $0 \leq x_i < 998244353 \ (0 \leq i < Q)$

出力

$Q$ 行出力してください。 $i$ 行目には $i$ 番目のクエリの答えを出力してください。

サンプル

サンプル1
入力
4 3
1 1
2 1
1 3
2 0
0 4 0 1
1 3 2 2
2 4 1 5
出力
16
5
13

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。