問題一覧 > 通常問題

No.1889 K Consecutive Ks (Hard)

レベル : / AI推定難易度 : 2625 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 23
作問者 : miscalc / テスター : akakimidori ygussany
お気に入りにしたユーザー ProblemId : 7079 / 自分の提出
問題文最終更新日: 2022-04-01 01:56:41
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 337 (順位表) の他の問題:

Problem Statement

This is the same problem as Problem E, but with different constraints and a different time limit.

Find the number of sequences $A = (A_1, A_2, \ldots, A_N)$ of length $N$ consisting of integers between $1$ and $M$, inclusive, that satisfy the following condition.

  • $A$ contains a place where some positive integer $k$ appears $k$ times consecutively. That is, there exist positive integers $i, k$ ($i + k - 1 \leq N$) such that $A_i = A_{i + 1} = \cdots = A_{i + k - 1} = k$.
Since the answer can be very large, output the remainder when divided by $998244353$.

Input

$N$ $M$

  • All inputs are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$

Output

Output the number of sequences $A$ satisfying the condition, modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
2 3
Output
6

The following $6$ sequences $A$ satisfy the condition.

  • $(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)$ contain a place where $1$ appears $1$ time consecutively.
  • $(2, 2)$ contains a place where $2$ appears $2$ times consecutively.

Sample 2
Input
5 4
Output
884

Here are some examples of sequences $A$ satisfying the condition.

  • $(4, 2, 4, 1, 3)$ contains a place where $1$ appears $1$ time consecutively.
  • $(4, 3, 3, 3, 2)$ contains a place where $3$ appears $3$ times consecutively.
  • $(2, 2, 4, 2, 2)$ contains a place where $2$ appears $2$ times consecutively.
  • $(2, 2, 3, 3, 3)$ contains a place where $2$ appears $2$ times consecutively and a place where $3$ appears $3$ times consecutively.
  • $(3, 3, 3, 3, 3)$ contains a place where $3$ appears $3$ times consecutively.

Sample 3
Input
200000 200000
Output
602367127

Output the remainder when divided by $998244353$.

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