問題一覧 > 通常問題

No.1889 K Consecutive Ks (Hard)

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : miscalc / テスター : akakimidori 👑 ygussany
6 ProblemId : 7079 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-01 01:56:41

問題文

問題 E と同じ問題ですが、制約と実行時間制限が異なります。

1 以上 M 以下の整数からなる長さ N の数列 A=(A1,A2,…,AN) であって、次の条件を満たすようなものの個数を求めてください。

  • A には、ある正の整数 k が k 個連続して現れる箇所がある。すなわち、ある正の整数 i,k（i+k−1≤N）が存在して、Ai=Ai+1=⋯=Ai+k−1=k を満たす。
答えは非常に大きくなることがあるので、998244353 で割った余りを出力してください。

入力

N M

  • 入力はすべて整数である
  • 1≤N≤2×105
  • 1≤M≤2×105

出力

条件を満たす A の個数を 998244353 で割った余りを出力してください。最後に改行してください。

サンプル

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

条件を満たす A は以下の 6 つです。

  • (1,1),(1,2),(1,3),(2,1),(3,1) には、1 が 1 個連続して現れる箇所があります。
  • (2,2) には、2 が 2 個連続して現れる箇所があります。

サンプル2
入力
5 4
出力
884

条件を満たす A の例を挙げます。

  • (4,2,4,1,3) には、1 が 1 個連続して現れる箇所があります。
  • (4,3,3,3,2) には、3 が 3 個連続して現れる箇所があります。
  • (2,2,4,2,2) には、2 が 2 個連続して現れる箇所があります。
  • (2,2,3,3,3) には、2 が 2 個連続して現れる箇所、3 が 3 個連続して現れる箇所があります。
  • (3,3,3,3,3) には、3 が 3 個連続して現れる箇所があります。

サンプル3
入力
200000 200000
出力
602367127

998244353 で割った余りを出力してください。

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