問題一覧 > 通常問題

No.1516 simple 門松列 problem Re:MASTER

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 42
作問者 : ansainansain / テスター : akakimidoriakakimidori
0 ProblemId : 6285 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-19 03:07:56

作問者より

C問題とは、制約と実行制限時間のみが異なります。
・python,pypyでのACは確認していますが、低速な言語では実装次第で間に合わない可能性があります。

問題文

3つの要素から成る数列 $v=(a_1,a_2,a_3)$ が次の条件を満たす時, $v$ は門松列であると言い伝えられています。
1.$a_1,a_2,a_3$ は全て異なる
2.3つの要素のうち $a_2$ が最も大きい,あるいは最も小さい
さらに, $n$ 個の要素(ただし $3≦n$) から成る数列$ w=(a_1,a_2....,a_n)$ が
どの連続した3つの要素を取り出しても門松列であるとき $w$ は門松列列であると言います。

長さ $N$ の整数列であって、数列の各要素が $0$ 以上 $K$ 未満であるものは $K^N$ 通りありますが、そのうち門松列列であるものが $ans_1$ 通りであるとします。$ans_1$を $998244353$ で割った余りを出力してください。
さらに、 $ans_1$ 通りの門松列列すべてにおいて、それぞれ数列の和を計算し、合計したものを $ans_2$ とします。 $ans_2$ を $998244353$ で割った余りを出力してください。

入力

$N\ K$

$3≦N≦10^9$
$3≦K≦9$
$N,K$ は整数である。

出力

$ans_1$と$ans_2$をそれぞれ$998244353$で割った余りを半角スペース区切りで出力してください。
最後に改行してください。

サンプル

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

$(0,2,1)$
$(1,2,0)$
$(1,0,2)$
$(2,0,1)$
の $4$ 通りあり、これらの数列の和を合計すると $12$ になります。

サンプル2
入力
6 9
出力
26124 626976

サンプル3
入力
75432 9
出力
27800053 805337678

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

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