← 返回题目列表

AtCoder · abc226_f

I. 排列分数

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

分数: 500 点

问题陈述

对于排列 P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N),让我们定义分数 S(P) of P 如下。

  • 有 N 人,已编号 1,2,\dots,N。此外,还有《Snuke》。最初,人 i (1 \leq i \leq N) 有球 i.
    每次 Snuke 尖叫时,每个人 i 这样 i \neq p_i 将球交给 Person p_i 同时进行。
    如果每个人至少尖叫一次后 i 有球 i,Snuke 停止尖叫。
    分数是 Snuke 尖叫直至停止的次数。这里,保证分数是有限值。

有 N! 排列 P of (1,2, \dots, N)。求总和,取模 998244353,这些排列的分数,每个都提高到 K次方。

  • 正式地,让 S_N 是以下排列的集合 (1,2, \dots, N)。计算如下: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

约束

  • 2 \leq N \leq 50
  • 1 \leq K \leq 10^4
  • 输入中的所有值都是整数。

输入

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

N K

输出

打印 \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.


示例输入 1

2 2

示例输出 1

5

当 N = 2,有两种可能的排列 P: (1,2),(2,1).

排列的分数 (1,2) 被发现如下。

  • 最初,人 1 有球 1和人 2 有球 2.
    Snuke的第一声尖叫之后,Person 1 有球 1和人 2 有球 2.
    在这里,每个人 i 有球 i,所以他停止尖叫。
    因此,分数是 1.

排列的分数 (2,1) 被发现如下。

  • 最初,人 1 有球 1和人 2 有球 2.
    Snuke的第一声尖叫之后,Person 1 有球 2和人 2 有球 1.
    Snuke第二次尖叫后,Person 1 有球 1和人 2 有球 2.
    在这里,每个人 i 有球 i,所以他停止尖叫。
    因此,分数是 2.

因此,本例的答案是 1^2 + 2^2 = 5.


示例输入 2

3 3

示例输出 2

79

下面列出了所有排列及其分数。

  • (1,2,3):分数是 1.
  • (1,3,2):分数是 2.
  • (2,1,3):分数是 2.
  • (2,3,1):分数是 3.
  • (3,1,2):分数是 3.
  • (3,2,1):分数是 2.

因此,我们应该打印 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.


示例输入 3

50 10000

示例输出 3

77436607