← 返回题目列表

AtCoder · awtf2025_e

E. 功能图

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

给你整数 N, C,和 K。 求模数 998244353,长度-N 整数序列 x=(x_1,x_2,\ldots,x_N) 满足以下条件。

  • 1 \leq x_i \leq N (1 \leq i \leq N).
  • 考虑一个无向图 N 顶点编号自 1 to N。 该图有 N 边缘,以及 i第一条边连接顶点 i 和 x_i。 那么,图的连通分量的数量正好是 C.
  • 数量 i 满意 i<x_i 正是 K.

约束

  • 1 \leq N \leq 250000
  • 1 \leq C \leq N
  • 0 \leq K \leq N-1
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N C K

输出

输出答案。


示例输入 1

3 1 2

示例输出 1

6

以下六个序列 x 满足条件:

  • x=(2,3,1)
  • x=(2,3,2)
  • x=(2,3,3)
  • x=(3,3,1)
  • x=(3,3,2)
  • x=(3,3,3)

示例输入 2

3 2 2

示例输出 2

0

示例输入 3

6 3 0

示例输出 3

225

示例输入 4

20 4 7

示例输出 4

476087626

示例输入 5

250000 2025 125000

示例输出 5

410390562