問題一覧 > 通常問題

No.3273 Exactly One Match

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : apricity / テスター : 遭難者
ProblemId : 12468 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-12 02:34:50

問題文

正整数 $N,K$ が与えられます． $1$ 以上 $N$ 以下の整数からなる長さ $N$ の数列 $A = (A_1, A_2, \dots, A_N)$ と， $1$ 以上 $K$ 以下の整数からなる長さ $N$ の数列 $C = (C_1, C_2, \dots, C_N)$ の組は $(NK)^N$ 通り考えられますが，そのうち次の条件を満たすものの数を $998244353$ で割った余りを求めてください．

  • $C_i = C_{A_i}$ を満たす $1$ 以上 $N$ 以下の整数 $i$ が ちょうど一つ 存在する．

入力

$N\ K$

  • 入力は全て整数
  • $1 \le N \le 10^6$
  • $1 \le K \le 10^{18}$

出力

条件を満たす $A$ と $C$ の組の数を $998244353$ で割った余りを出力してください．

サンプル

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

条件を満たす $A$ と $C$ の組は以下の $12$ 通りです．

  • $A = (1,1), C = (1,2)$
  • $A = (1,1), C = (1,3)$
  • $A = (1,1), C = (2,1)$
  • $A = (1,1), C = (2,3)$
  • $A = (1,1), C = (3,1)$
  • $A = (1,1), C = (3,2)$
  • $A = (2,2), C = (1,2)$
  • $A = (2,2), C = (1,3)$
  • $A = (2,2), C = (2,1)$
  • $A = (2,2), C = (2,3)$
  • $A = (2,2), C = (3,1)$
  • $A = (2,2), C = (3,2)$

サンプル2
入力
271 828
出力
516955559

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

サンプル3
入力
1000000 1839286755214161
出力
130737125

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