問題一覧 > 通常問題

No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 110
作問者 : mfbgjsczmfbgjscz / テスター : harady_a_humanharady_a_human
17 ProblemId : 4379 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-03 02:37:00

問題文

ここに$N$個の箱があります。$i(1\leq i\leq N)$個目の箱には玉が$A_i$個入っています。
より具体的に，箱$i$には，色$1$から色$A_i$までのすべての色の玉が$1$個ずつ入っています．
このとき,$Q$個のクエリに答えてください。$i(1\leq i\leq Q)$個目のクエリは，次の通りです。

  • それぞれの箱から玉を1つずつ取り出したとき,色$l_i$から色$r_i$についてその色の玉が$p_i$個含まれる場合の数を$mod998244353$で全て求め,その排他的論理和を$mod998244353$で出力して下さい．

    • 入力

    $N\ Q$
$A_1\ A_2\ ...\ A_N$
$l_1\ r_1\ p_1$
$l_2\ r_2\ p_2$
.
.
.
$l_Q\ r_Q\ p_Q$

    $1\le N\le 6000$
    $1\le Q\le 5000$
    $1\le A_i\le 10^9$
    $1\le l_i\le r_i\le max(A_1,A_2,...,A_N)$
    $0\le r_i-l_i\le 200$
    $0\le p_i\le N$
    入力はすべて整数

    出力

    $Q$個のクエリに答えて，最後に改行してください。

    サンプル

    サンプル1
    入力
    3 4
3 4 5
1 5 0
1 5 1
1 5 2
1 5 3
    出力
    12
3
10
1

    各クエリについて，答えを$998244353$で割ったあまりの排他的論理和を$998244353$で割ったあまりを出力することに注意して下さい．

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