No.2384 Permutations of Permutations
タグ : / 解いたユーザー数 17
作問者 :
箱星
/ テスター :
noshi91
問題文
$S$ を $\{1,2,\ldots,N\}$ 上の全単射全体の集合、$\mathcal{T}$ を $S$ 上の全単射 $F$ であって次を満たすものからなる集合とします。
- 任意の $f_1,f_2\in S$ に対して、$F(f_2\circ f_1)=F(f_2)\circ F(f_1)$
次の条件を満たす $\mathcal{T}$ の元 $F$ の個数を $998244353$ で割った余りを求めてください。
条件: $f\in S$ を $$ f(x)=\begin{cases} x+1 & (1\le x\lt K) \\ 1 & (x=K) \\ x & (K\lt x\le N) \end{cases} $$ により定めたとき $$ \begin{align*} F(f)(x) &= x+1 \quad (1\le x\lt K) \\ F(f)(K) &= 1 \end{align*} $$ を満たす。
制約
- $2\le N\le 10^5$
- $2\le K\le N$
- 入力はすべて整数
入力
$N$ $K$
出力
条件を満たす $\mathcal{T}$ の元 $F$ の個数を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
3 2
出力
2
$f\in S$ は $f(1)=2, f(2)=1, f(3)=3$ をみたす全単射です。
サンプル2
入力
1742 641
出力
990581483
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。