問題一覧 > 通常問題

No.2833 Count Taiko Results

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : twitteryou / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10942 / 自分の提出
問題文最終更新日: 2024-07-31 22:30:54
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 439 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。