問題一覧 > 通常問題

No.2670 Sum of Products of Interval Lengths

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : suisensuisen / テスター : cureskolcureskol ygussanyygussany kaichou243kaichou243
1 ProblemId : 10305 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-11 22:17:24

問題文

正整数 $n,m$ が与えられます。

各要素が $1$ 以上 $m$ 以下の整数であるような長さ $n$ の整数列 $A = (A _ 1, A _ 2, \ldots, A _ n)$ に対して、$1\leq l\leq r\leq n$ を満たす整数組 $(l,r)$ が よい組 であるとは、次が成り立つことを言います。

  • 全ての $i = 0, 1, \ldots, r - l$ に対して $A _ {l + i} = A _ l + i$ を満たす

また、整数列 $(x _ 1, x _ 2, \ldots, x _ k)$ が よい列 であるとは、次の $2$ つが全て成り立つことを言います。

  • $1 = x _ 1\lt x _ 2\lt \cdots \lt x _ k = n + 1$
  • 全ての $i = 1,2,\ldots,k - 1$ に対して、組 $(x _ i, x _ {i + 1} - 1)$ は よい組 である

任意の $A$ に対して長さ最小の よい列 $x$ が一意に定まることを証明できるので、これを $x ^ \ast = (x ^ \ast _ 1, x ^ \ast _ 2, \ldots, x ^ \ast _ k)$ とします。そして、$A$ の スコア $f(A)$ を次で定義します。

$$f(A)\coloneqq\prod _ {i = 1} ^ {k - 1} (x ^ \ast _ {i + 1} - x ^ \ast _ i).$$

各要素が $1$ 以上 $m$ 以下の整数であるような長さ $n$ の整数列 $A$ は $m ^ n$ 通り存在しますが、その全てに対する スコア の総和を $998244353$ で割ったあまりを求めてください。

入力

入力は以下の形式で標準入力から与えられます。

$n\ m$
  • 入力は全て整数で与えられる。
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq m\leq 10 ^ {18}$

出力

答えを $1$ 行に出力して改行してください。

サンプル

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

この入力は $n=3,\ m=2$ を表します。$A$ としてあり得るものは $(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$ の $8$ つあります。

例えば $A = (1,1,2)$ に対して、よい列 は $x = (1,2,3,4)$ と $x = (1,2,4)$ の $2$ つ存在しますが、このうち長さ最小のものは $x ^ \ast = (1,2,4)$ です。従って、この $A$ に対するスコアは $(2 - 1) \times (4 - 2) = 2$ と定まります。

$(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$ に対するスコアはそれぞれ $1,2,2,2,1,2,1,1$ であることが確かめられるので、答えとしてその総和である $12$ を出力してください。

サンプル2
入力
200000 1000000000000000000
出力
156232207

スコア の総和を $998244353$ で割ったあまりを出力してください。

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