Bags with Balls

题意翻译

# Bags with Balls 袋中之球 ## 题目描述 这里有 $ n $ 个袋子，每个袋子里面有 $ m $ 个带有从 $ 1 $ - $ m $ 标记的球。对于每一个 $ 1 $ ≤ $ i $ ≤ $ m $ 来说，每个袋子中都一定存在一个带有 $ i $ 标记的球。 你需要在每个袋子中取出一个球 ( 所有的袋子都是不同的，比如在 $ 1 $ 号袋子取 $ 2 $ 号球 并且从 $ 2 $ 号袋子里取 $ 1 $ 号球 与 从 $ 1 $ 号袋子取 $ 1 $ 号球并且从 $ 2 $ 号袋子取 $ 2 $ 号球是不同的两种方案 ) 然后计算出你取出的标号是奇数的球的数量，记这个数量为 $ F $ 。 你的任务是计算所有可能的取球方案的 $ F^k $ 之和。 ## 输入格式 第一行包含一个整数 $ t $ ( $ 1 \le t \le 5000 $ ) — 测试组数的数量 每组第一行输入三个整数 $ n $ , $ m $ 和 $ k $ ( $ 1 \le n, m \le 998244352 $ ; $ 1 \le k \le 2000 $ ). ## 输出格式 每组测试输出一个整数 — $ F^k $ ( 意义见题面 ). 由于它可能会很大，请将它模 $ 998244353 $ 后输出.

题目描述

There are $ n $ bags, each bag contains $ m $ balls with numbers from $ 1 $ to $ m $ . For every $ i \in [1, m] $ , there is exactly one ball with number $ i $ in each bag. You have to take exactly one ball from each bag (all bags are different, so, for example, taking the ball $ 1 $ from the first bag and the ball $ 2 $ from the second bag is not the same as taking the ball $ 2 $ from the first bag and the ball $ 1 $ from the second bag). After that, you calculate the number of balls with odd numbers among the ones you have taken. Let the number of these balls be $ F $ . Your task is to calculate the sum of $ F^k $ over all possible ways to take $ n $ balls, one from each bag.

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 5000 $ ) — the number of test cases. Each test case consists of one line containing three integers $ n $ , $ m $ and $ k $ ( $ 1 \le n, m \le 998244352 $ ; $ 1 \le k \le 2000 $ ).

输出格式

For each test case, print one integer — the sum of $ F^k $ over all possible ways to take $ n $ balls, one from each bag. Since it can be huge, print it modulo $ 998244353 $ .

输入输出样例

输入样例 #1

5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000

输出样例 #1

1028
1
3
729229716
652219904

题目大意：
这个题目是关于从多个袋子中取球的。有n个袋子，每个袋子里有m个标号为1到m的球，每个袋子中都有恰好一个标号为i的球（对于每个i从1到m）。你需要从每个袋子中取出一个球（所有袋子都是不同的，所以不同的取球顺序被视为不同的方案），然后计算出你取出的标号为奇数的球的数量，记为F。任务是计算所有可能的取球方案中F^k的和。

输入数据格式：
第一行包含一个整数t（1≤t≤5000），表示测试组数的数量。
每组输入包含三个整数n, m和k（1≤n, m≤998244352；1≤k≤2000）。

输出数据格式：
对于每组测试，输出一个整数，即所有可能的取球方案中F^k的和模998244353后的结果。

输入输出样例：
输入样例 #1:
5
2 3 8
1 1 1
1 5 10
3 7 2000
1337666 42424242 2000

输出样例 #1:
1028
1
3
729229716
652219904题目大意： 这个题目是关于从多个袋子中取球的。有n个袋子，每个袋子里有m个标号为1到m的球，每个袋子中都有恰好一个标号为i的球（对于每个i从1到m）。你需要从每个袋子中取出一个球（所有袋子都是不同的，所以不同的取球顺序被视为不同的方案），然后计算出你取出的标号为奇数的球的数量，记为F。任务是计算所有可能的取球方案中F^k的和。 输入数据格式： 第一行包含一个整数t（1≤t≤5000），表示测试组数的数量。 每组输入包含三个整数n, m和k（1≤n, m≤998244352；1≤k≤2000）。 输出数据格式： 对于每组测试，输出一个整数，即所有可能的取球方案中F^k的和模998244353后的结果。 输入输出样例： 输入样例 #1: 5 2 3 8 1 1 1 1 5 10 3 7 2000 1337666 42424242 2000 输出样例 #1: 1028 1 3 729229716 652219904