[AGC039F] Min Product Sum
题意翻译
- 有一个大小为 $N \times M$ 的矩阵。矩阵中每个数的取值都是 $[1, K]$。
- 对于一个矩阵,定义函数 $f(x,y)$ 为:第 $x$ 行和第 $y$ 列的一共 $N + M - 1$ 个数中的最小值。
- 对于一个矩阵,定义其权值为 $\prod_{x=1}^{N}\prod_{y=1}^{M}f(x,y)$。
- 你需要求出,对于所有 $K^{NM}$ 种矩阵,每个矩阵的权值和对 $D$ 取模的结果。
- $1 \leq N, M, K \leq 100$,$10^8 \leq D \leq 10^9$,保证 $D$ 为质数。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc039/tasks/agc039_f
$ N $ 行 $ M $ 列のマス目の全てのマスに $ 1 $ 以上 $ K $ 以下の整数を書き込む方法 $ K^{NM} $ 通りすべてに対して以下の値を求め、 それらすべての総和を $ D $ で割ったあまりを求めてください。
- $ NM $ 個の各マスに対し、それと同じ行あるいは同じ列のマス (自分自身を含む) に書かれた整数の最小値を求め、それら $ NM $ 個すべての積を取って得られる値
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ K $ $ D $
输出格式
$ K^{NM} $ 個の値の総和を $ D $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
2 2 2 998244353
输出样例 #1
35
输入样例 #2
2 3 4 998244353
输出样例 #2
127090
输入样例 #3
31 41 59 998244353
输出样例 #3
827794103
说明
### 制約
- $ 1\ \leq\ N,M,K\ \leq\ 100 $
- $ 10^8\ \leq\ D\ \leq\ 10^9 $
- $ N,M,K,D $ は整数である
- $ D $ は素数である
### Sample Explanation 1
$ NM $ 個の値の積が $ 16 $ になる書き込み方が $ 1 $ 通り、$ 2 $ になる書き込み方が $ 4 $ 通り、$ 1 $ になる書き込み方が $ 11 $ 通りあります。