問題一覧 > 通常問題

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

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

No.1066とこの問題は同じ問題ですが,制約と実行時間制限とメモリ制限が異なります。(21:30追記)

問題文

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

  • それぞれの箱から玉を1つずつ取り出したとき,色$1$の玉が$B_i$個含まれる場合の数を$mod998244353$で出力して下さい.

  • 入力

    $N\ Q$
    $A_1\ A_2\ ...\ A_N$
    $B_1\ B_2\ ...\ B_Q$
    

    $1\le N\le 2\times 10^5$
    $1\le Q\le min(N+1,5000)$
    $1\le A_i\le 10^{18}$
    $0\le B_i\le N$
    入力はすべて整数

    出力

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

    サンプル

    サンプル1
    入力
    3 4
    3 4 5
    0 1 2 3
    出力
    24
    26
    9
    1

    玉の取り方は全部で$60$通りあります.そのうち色$1$の玉が$1$つも含まれないような取り方は$24$通りあります.

    サンプル2
    入力
    4 3
    1 3 3 3
    3 1 4
    出力
    6
    8
    1

    サンプル3
    入力
    3 2
    5 7 5
    1 3
    出力
    64
    1

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