問題一覧 > 通常問題

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

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

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

問題文

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

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

    • 入力

    N Q
A1 A2 ... AN
B1 B2 ... BQ

    1≤N≤2×105
    1≤Q≤min(N+1,5000)
    1≤Ai≤1018
    0≤Bi≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。