No.2833 Count Taiko Results
タグ : / 解いたユーザー数 21
作問者 :
Problem Statement
A certain popular Japanese drum game has evolved in the near future and made its return. Its judgments have also changed greatly from the conventional ones, and they now vary for each note.
Now, a play of a song with $N$ notes has just finished. For the $i\ (1 \leq i \leq N)\ $-th note of this song, there are $A_i+B_i\ $ levels of judgment; with one of the top $A_i$ kinds of judgment the combo continues, and with one of the bottom $B_i$ kinds of judgment the combo is broken.
Now, it is known from the result that the maximum combo was $K$ combo. Find the number of such results, modulo $998244353$.
$2$ results are distinguished if the judgment of some note differs.
Explanation of terms
A note means a musical note, a combo is the number of notes hit consecutively with a judgment in the top $A_i$ levels, the maximum combo is the largest of the combos until the song ends, and a result is the record on which the performance is written.
Input
$N\ K$ $A_1 \ A_2 \ \ldots \ A_N$ $B_1 \ B_2 \ \ldots \ B_N$
・$1 \leq N \leq 2 \times 10^5$
・$1 \leq K \leq N$
・$1 \leq A_i,B_i \leq 10^8\ (1 \leq i \leq N)$
・$N,K,A_i,B_i\ (1 \leq i \leq N)\ $ are all integers
Output
Output the number of results whose maximum combo is $K$, modulo $998244353$.
Sample
Sample 1
Input
3 2 2 2 2 1 1 1
Output
8
Let the judgments be
p,g,b from the top, with the combo broken only by b. Then the $8$ results ppb,pgb,gpb,ggb,bpp,bpg,bgp,bgg are those with a maximum combo of $2$.
Results such as
pbp and ppg have maximum combos of $1$ and $3$ respectively, so they do not satisfy the condition.
Sample 2
Input
2 2 1 3 3 1
Output
3
Sample 3
Input
3 2 1 1 1 51543 45318957 51345
Output
102888
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。