Many Good Tuple Problems

题目描述

本题中“好序列对”的定义与问题 D 中相同。

长度为 $M$ 且由不超过 $N$ 的正整数组成的一个序列对 $(S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M))$ 被称为好序列对当且仅当 $(S, T)$ 满足下列条件。

存在一个长度为 $N$、由 $0$ 和 $1$ 组成的序列 $X = (X_1, X_2, \dots, X_N)$，使得对于每个 $i=1, 2, \dots, M$ 都有： $X_{S_i} \neq X_{T_i}$。

在所有 $N^{2M}$ 个可能的长度为 $M$ 且由不超过 $N$ 的正整数组成的序列对 $(A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M))$ 中，求满足为好序列对的个数对 $998244353$ 取模后的值。

输入格式

输入由标准输入给出，格式如下： $N$ $M$

输出格式

输出长度为 $M$ 且由不超过 $N$ 的正整数组成的好序列对的个数对 $998244353$ 取模后的值。

3 2

36

3 3

168

12 34

539029838

20 231104

966200489

提示

$1 \leq N \leq 30$ $1 \leq M \leq 10^9$ $N$ 和 $M$ 是整数。例如，如果 $A=(1,2), B=(2,3)$，那么 $(A, B)$ 是一个好序列对。事实上，如果我们取 $X=(0,1,0)$，则 $X$ 是一个长度为 $N$、由 $0$ 和 $1$ 组成的序列，且满足 $X_{A_1} \neq X_{B_1}$ 和 $X_{A_2} \neq X_{B_2}$。因此，$(A, B)$ 满足作为好序列对的条件。
共有 $36$ 个好序列对，因此输出该数。

标签: AtCoder|abc327G

来源

AtCoder|abc327G