問題一覧 > 通常問題

No.2833 Count Taiko Results

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : ねしんねしん / テスター : 👑 p-adicp-adic
0 ProblemId : 10942 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-31 22:30:54

問題文

某人気和太鼓ゲームが近未来で進化して帰ってきました。判定も従来のものと大きく変わり、それぞれのノーツごとに判定が変わるようになりました。
今、ノーツ数が$N$である曲のプレイが終わりました。この曲の判定は$i\ (1 \leq i \leq N)\ $番目のノーツでは、$A_i+B_i\ $段階の判定があり、上から$A_i$種類の判定なら、コンボをつなげ、下から$B_i$種類の判定ではコンボが途切れてしまいます。
今、リザルトから最大コンボが$K$コンボであることが判明しています。このようなリザルトの数を$998244353$で割った余りを求めてください。
$2$つのリザルトはあるノーツの判定が異なるとき区別されます。

用語の説明

ノーツとは音符のこと、コンボは連続して上位$A_i$段階の判定で叩けた数、最大コンボは曲が終わるまでの間のコンボの中で最大のもの、リザルトは成績が記されたもののことを意味します。

入力

$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)\ $はすべて整数

出力

最大コンボが$K$であるリザルトの数を$998244353$で割った余りを出力してください。

サンプル

サンプル1
入力
3 2
2 2 2
1 1 1
出力
8

それぞれの判定を上からp,g,bとし、bでのみコンボが途切れるとすると、ppb,pgb,gpb,ggb,bpp,bpg,bgp,bggの$8$つが最大コンボが$2$のリザルトになります。
pbpやppgなどはそれぞれ最大コンボが$1$、$3$であるため条件に当てはまりません。

サンプル2
入力
2 2
1 3
3 1
出力
3

サンプル3
入力
3 2
1 1 1
51543 45318957 51345
出力
102888

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