3D Combinatorics PTSD

3D Combinatorics PTSD

Combinatorics PTSD

时间限制:1s

空间限制:64MB

题目描述

\[\bold{Calculate\ \ \ {\LARGE |} \{\bold{(a_0,a_1...a_{n-1})}\ {\big |}\ \forall i\in \{0,1,..., n-1\},a_i\in \{1,2,...,k\} ∧ a_i\neq a_{((i+1)\mod n)}\}{\LARGE |} \mod 998244353}\]

输入格式

两个正整数 \(n,k\) ,同题目描述所示。

输出格式

输出答案,注意,方案数需要对 998244353 取模。

样例输入1

3 3

样例输出1

6

样例1解释

题意翻译
image-20220412175928033

\((1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)\) 一共六种符合条件的3元组。

样例输入2

4 4

样例输出2

84

样例2解释

部分可行的方案:

(1,2,1,2)(1,2,1,3)(1,2,1,4)(1,2,3,2)(1,2,3,4)(1,2,4,2)(1,2,4,3)(1,3,1,2)(1,3,1,3)(1,3,1,4)

(1,3,2,3)(1,3,2,4)

样例输入3

1926 817

样例输出3

164477364

数据范围

对于 50 % 的数据,\(2\le n,k\le 8\)

对于 100 % 的数据,\(2\le n,k \le 3*10^3\)

  • bonus: 如何对于 \(2\le n,k\le 10^{18}\) 求解?

信息

ID
1354
难度
8
分类
(无)
标签
(无)
递交数
29
已通过
5
通过率
17%
上传者

相关

在下列比赛中:

悬赏令第三周