luogu#P11057. 诈骗题

诈骗题

题目背景

这是一道诈骗题。

题目描述

定义 f(n,m)f(n,m) 为下列问题的答案。

考虑一个 n×mn\times m 黑白网格图,初始全是白色的。每次操作如下:

  • 选择一个白格子 (x,y)(x,y),将其所在行全染黑,这个操作叫 (x,y,R)(x,y,\text{R})
  • 选择一个白格子 (x,y)(x,y),将其所在列全染黑,这个操作叫 (x,y,C)(x,y,\text{C})

假设最多能操作 kk 次。问:

  • 对于所有操作 kk 次的方案,有多少种本质不同的 操作集合 。操作集合是一个大小为 kk 的集合,代表操作过的 kk 种操作。(注意,顺序不同但操作集合相同的 22 种方案只会被计算 11 次)

称两个操作集合 A,BA, B 本质不同,当且仅当存在某种操作 optopt,满足 [optA]+[optB]=1[opt \in A] + [opt \in B] = 1

现在给定 n,mn,m,请你对于所有 1in, 1jm1\le i\le n,\ 1\le j\le m 求出 f(i,j)f(i,j) 的取值。

由于答案可能有点大,因此你只需要输出其取模 998244353998244353 的结果。

输入格式

输入一行两个正整数 n,mn,m

输出格式

输出一个 nnmm 列的矩阵,第 ii 行第 jj 个数表示 f(i,j)mod998244353f(i,j)\bmod 998244353

2 2
2 3
3 16

提示

样例解释

对于 f(1,2)f(1, 2),此时 k=2k = 2,一共有以下 33 个可能的操作集合:

  • {(1,1,R),(1,2,C)}\{(1, 1, \text R), (1, 2, \text C)\}
  • {(1,1,C),(1,2,R)}\{(1, 1, \text C), (1, 2, \text R)\}
  • {(1,1,C),(1,2,C)}\{(1, 1, \text C), (1, 2, \text C)\}

注意到对于最后一个集合,有不止一种操作顺序,但是由于它们对应的操作集合相同,因此只被记入答案一次。

数据范围

洛谷代码长度限制为 50 KB\textbf{50\ KB}

测试点编号 n=n= m=m=
11 22
22 33
33 55
44 1010
55 2020
66 5050
77 100100
88 11 200200
99 22
1010 300300

对于所有数据,保证 1n,m3001\le n,m\le 300