CF1731F.Function Sum

省选/NOI-

通过率：0%

时间限制：4.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Suppose you have an integer array $a_1, a_2, \dots, a_n$ .

Let $\operatorname{lsl}(i)$ be the number of indices $j$ ( $1 \le j \lt i$ ) such that $a_j \lt a_i$ .

Analogically, let $\operatorname{grr}(i)$ be the number of indices $j$ ( $i \lt j \le n$ ) such that $a_j \gt a_i$ .

Let's name position $i$ good in the array $a$ if $\operatorname{lsl}(i) \lt \operatorname{grr}(i)$ .

Finally, let's define a function $f$ on array $a$ $f(a)$ as the sum of all $a_i$ such that $i$ is good in $a$ .

Given two integers $n$ and $k$ , find the sum of $f(a)$ over all arrays $a$ of size $n$ such that $1 \leq a_i \leq k$ for all $1 \leq i \leq n$ modulo $998\,244\,353$ .

假设你有一个整数数组 $a_1, a_2, \dots, a_n$ 。

令 $\operatorname{lsl}(i)$ 表示满足 $1 \le j \lt i$ 且 $a_j \lt a_i$ 的下标 $j$ 的个数。

类似地，令 $\operatorname{grr}(i)$ 表示满足 $i \lt j \le n$ 且 $a_j \gt a_i$ 的下标 $j$ 的个数。

若在数组 $a$ 中 $\operatorname{lsl}(i) \lt \operatorname{grr}(i)$ ，则称位置 $i$ 在数组 $a$ 中是好的。

最后，定义函数 $f$ 作用于数组 $a$ 上： $f(a)$ 等于所有满足“ $i$ 在 $a$ 中是好的”的 $a_i$ 的和。

给定两个整数 $n$ 和 $k$ ，求对所有长度为 $n$ 且满足 $1 \leq a_i \leq k$ （对所有 $1 \leq i \leq n$ ）的数组 $a$ ， $f(a)$ 的总和，并对 $998\,244\,353$ 取模。

输入格式

The first and only line contains two integers $n$ and $k$ ( $1 \leq n \leq 50$ ; $2 \leq k \lt 998\,244\,353$ ).

第一行且仅一行包含两个整数 $n$ 和 $k$ （ $1 \leq n \leq 50$ ； $2 \leq k \lt 998\,244\,353$ ）。

输出格式

Output a single integer — the sum of $f$ over all arrays $a$ of size $n$ modulo $998\,244\,353$ .

输出一个整数——对所有长度为 $n$ 的数组 $a$ 的 $f$ 值之和，结果对 $998\,244\,353$ 取模。

输入输出样例

输入#1
```
3 3
```
输出#1
```
28
```
输入#2
```
5 6
```
输出#2
```
34475
```
输入#3
```
12 30
```
输出#3
```
920711694
```

说明/提示

In the first test case:

$f([1,1,1]) = 0$

$f([2,2,3]) = 2 + 2 = 4$

$f([1,1,2]) = 1 + 1 = 2$

$f([2,3,1]) = 2$

$f([1,1,3]) = 1 + 1 = 2$

$f([2,3,2]) = 2$

$f([1,2,1]) = 1$

$f([2,3,3]) = 2$

$f([1,2,2]) = 1$

$f([3,1,1]) = 0$

$f([1,2,3]) = 1$

$f([3,1,2]) = 1$

$f([1,3,1]) = 1$

$f([3,1,3]) = 1$

$f([1,3,2]) = 1$

$f([3,2,1]) = 0$

$f([1,3,3]) = 1$

$f([3,2,2]) = 0$

$f([2,1,1]) = 0$

$f([3,2,3]) = 2$

$f([2,1,2]) = 1$

$f([3,3,1]) = 0$

$f([2,1,3]) = 2 + 1 = 3$

$f([3,3,2]) = 0$

$f([2,2,1]) = 0$

$f([3,3,3]) = 0$

$f([2,2,2]) = 0$

Adding up all of these values, we get $28$ as the answer.

在第一个测试用例中：