問題一覧 > 通常問題

No.1549 [Cherry 2nd Tune] BANning Tuple

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 21
作問者 : 👑 Kazun / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 6020 / 自分の提出
問題文最終更新日: 2021-06-19 01:11:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 299 (BANNED CONTEST) (順位表) の他の問題:

Problem Statement

Consider tuples $(X_1, \dots, X_N)$ of $N$ non-negative integers. Here, condition $i$ is defined as follows.

  • Condition $i$: $A_i \leq X_{K_i} \leq B_i$ does not hold.
For $q=1, \dots, Q$, answer the following question $q$.

Question $q$

Among the tuples $(X_1, \dots, X_N)$ of $N$ non-negative integers that satisfy all of condition $1$, $\dots$, condition $q$, how many satisfy $S_q \leq X_1+\dots+X_N \leq T_q$?

Since the answer can be very large, output it modulo $998244353$.

Constraints

  • $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$
  • All inputs are integers.

Input

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

Output

The output consists of $Q$ lines. On the $q$-th line, output the answer to question $q$ modulo $998244353$.

Sample

Sample 1
Input
2 3
1 1 4 3 6
2 2 5 3 4
1 2 3 4 10
Output
7
0
16

  • Condition $1$ is that $1 \leq X_1 \leq 4$ does not hold. Under this condition, the tuples satisfying $3 \leq X_1+X_2 \leq 6$ are limited to the following 7:
    $\quad (X_1,X_2)=(0,3), (0,4), (0,5), (0,6), (5,0), (5,1), (6,0)$
    .
  • Condition $2$ is that $2 \leq X_2 \leq 5$ does not hold. For $(X_1, X_2)$ satisfying both conditions $1,2$, $3 \leq X_1+X_2 \leq 4$ never holds. Note here that conditions introduced earlier remain in effect.
  • Condition $3$ is that $2 \leq X_1 \leq 3$ does not hold, but this is contained in condition $1$. In this way, an added condition is not necessarily useful.

Sample 2
Input
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
Output
337715468
158601612
966758812
511143361
460066854

Do not forget to output the answer modulo $998244353$.

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