問題一覧 > 通常問題

No.3273 Exactly One Match

レベル : / AI推定難易度 : 2700 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : apricity / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 12468 / 自分の提出
問題文最終更新日: 2025-09-12 02:34:50
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 482 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,K$. There are $(NK)^N$ possible pairs of a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ consisting of integers between $1$ and $N$, inclusive, and a sequence $C = (C_1, C_2, \dots, C_N)$ of length $N$ consisting of integers between $1$ and $K$, inclusive. Find the number, modulo $998244353$, of such pairs that satisfy the following condition.

  • There exists exactly one integer $i$ between $1$ and $N$, inclusive, such that $C_i = C_{A_i}$.

Input

$N\ K$

  • All input values are integers.
  • $1 \le N \le 10^6$
  • $1 \le K \le 10^{18}$

Output

Output the number, modulo $998244353$, of pairs of $A$ and $C$ that satisfy the condition.

Sample

Sample 1
Input
2 3
Output
12

The following $12$ pairs of $A$ and $C$ satisfy the condition.

  • $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)$

Sample 2
Input
271 828
Output
516955559

Output the answer modulo $998244353$.

Sample 3
Input
1000000 1839286755214161
Output
130737125

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