No.1549 [Cherry 2nd Tune] BANning Tuple
問題文最終更新日: 2021-06-19 01:11:13
English (AI translation)
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
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
Nachia