#PQJ1455x7974. QOJ 1455_7974
QOJ 1455_7974
标题: 染色 - Problem - QOJ.ac
#7974. 染色
The problem was used in the following contests:
给定一个 N×M 的网格图,每个格子初始为白色,现在需要将 K 个格子染成黑色,使得每行每列的黑格子数均为奇数,求方案数。
输入格式
一行三个整数 N,M,K。
输出格式
输出一行一个整数,表示方案数 mod998244353 的结果。
样例一
input
3 3 5
output
9
样例二
input
500 1000 1000
output
928165755
数据范围
测试点编号N,MK1,2N×M≤203,4N×M≤1005,6N×M≤5000K≤1007,8N×M≤50009,10,11N×M≤10512,13N×M≤5×105K∈{N,M}14,15N×M≤5×105K≤100016,17,18,19,20N×M≤5×105
对于所有数据,保证 N,M 为正整数,0≤K≤N×M,对于所有编号为偶数的点,有 N=M。