問題一覧 > 通常問題

No.1549 [Cherry 2nd Tune] BANning Tuple

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : KazunKazun / テスター : NachiaNachia
0 ProblemId : 6020 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-09 22:24:27

問題文

$N$ 個の非負整数からなる整数の組 $(X_1, \dots, X_N)$ について考える. ここで, 条件 $i$ を以下のように設定する.

  • 条件 $i$: $A_i \leq X_{K_i} \leq B_i$ を満たさない.
$q=1, \dots, Q$ に対して, 以下の質問 $q$ に答えよ.

質問 $q$

条件 $1$, $\dots$, 条件 $q$ を全て満たす $N$ 個の非負整数の組 $(X_1, \dots, X_N)$ のうち, $S_q \leq X_1+\dots+X_N \leq T_q$ を満たすのはいくつか?

ただし, 解答は非常に大きくなりうるので, 出力の際には $998244353$ で割った余りを出力せよ.

制約

  • $1 \leq N \leq 10^{18}$
  • $1 \leq Q \leq 100$
  • $1 \leq K_i \leq N $
  • $0 \leq A_i \leq B_i \leq 3000$
  • $0 \leq S_i \leq T_i \leq 3000$
  • 入力はすべて整数である.

入力

$N$ $Q$
$K_1$ $A_1$ $B_1$ $S_1$ $T_1$
$\vdots$
$K_Q$ $A_Q$ $B_Q$ $S_Q$ $T_Q$

出力

出力は $Q$ 行からなる. $q$ 行目には, 質問 $q$ に対する解答を $998244353$ で割った余りを出力せよ.

サンプル

サンプル1
入力
2 3
1 1 4 3 6
2 2 5 3 4
1 2 3 4 10
出力
7
0
16

  • 条件 $1$ は, $1 \leq X_1 \leq 4$ を満たさないことである. この条件下で, $3 \leq X_1+X_2 \leq 6$ を満たすのは,
    $\quad (X_1,X_2)=(0,3), (0,4), (0,5), (0,6), (5,0), (5,1), (6,0)$
    の7個に限られる.
  • 条件 $2$ は, $2 \leq X_2 \leq 5$ を満たさないことである. 条件 $1,2$ を両方満たすような $(X_1, X_2)$ において, $3 \leq X_1+X_2 \leq 4$ となることはない. ここで, 前に発生した条件も残ることに注意せよ.
  • 条件 $3$ は, $2 \leq X_1 \leq 3$ を満たさないことであるが, これは条件 $1$ を含んでいる. このように, 追加される条件が必ずしも有用であるとは限らない.

サンプル2
入力
1000 5
141 42 135 62 373
223 606 797 749 978
331 66 247 90 2553
271 82 818 2845 2845
314 159 265 0 3000
出力
337715468
158601612
966758812
511143361
460066854

$998244353$ で割った余りを出力することを忘れないこと.

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