题目描述

小度在公园玩一个染色游戏，染色板为一个长为$n$，宽为 $m$ 的长方形网格，一开始它们的颜色都是白色。
小度的颜料可以将其中的 $k$ 个的格子染成黑色，颜料需要用完，且不能重复染色。
最终的要求是任意相邻两行或任意相邻两列要么保证完全一致，要么完全不一致。

完全一致指相邻行/列中相邻的格子要么同为白色，要么同为黑色。
完全不一致指相邻行/列中相邻的格子一个为白色，一个为黑色。

请计算有多少种染色方案。

输入格式：

一行，三个整数 $n$,$m$,$k$ ($ 1 \leq n , m \leq 10^7 $ , $0 \leq k \leq n×m$) 。

输出格式：

一行，输出答案，由于答案过大所以输出答案对 $998244353$ 取模的结果。

样例

输入：

2 2 2

输出：

6

题目分析

要点：组合数学 线性逆元

首先看题干要求，有一点很苛刻，“任意相邻两行或任意相邻两列要么保证完全一致，要么完全不一致”
这个条件就确定了如果我们从第一行开始填充之后，后面的行就是确定的了，不然完全相同，不然完全相反
所以我们的思路就明确了许多，枚举第一行可以填充的黑色块个数，这样就可以求出所有方案数

设第一行填$i$个黑色块 ， 则与第一行完全相反的有$m - i$个黑色块
注意这里$0 \le i \le \frac{m}{2}$ 是因为枚举$\frac{m}{2}$以上的数时其对应的相反的方案其实在之前已经计算过了
比如 在枚举$i = 0$时 其实已经验证并计算了$i = m$的可行性和方案数
再设$n$行中一共有y行和第一行相同 ，则有$n - y$行与第一行完全相反

那么一共有黑色块 $i * y + (m - i) * (n - y)$ 个
又黑色块共有$k$个
所以
$k = i * y + (m - i) * (n - y)$
化简得
$ y = \frac{(m - i) * n - k}{-2i + m} $

很明显 $y$ 得是整数并且$ 0 \le y \le n$

有了$y$之后就是求方案数了
首先是从$n$行中取出$y$行和枚举的行相同 $C_{n}^{y}$
还有选取枚举行中选择涂黑的格子 $C_{m}^{i}$
相乘便是这种选择下的方案数

还有要注意下 $m$是否是偶数，是的话要看一下当正好取值$\frac{m}{2}$时是否正好满足，满足的话也要加进总方案数中

时间复杂度$O(max${$n , m$}$)$

然后就是这道题目数很大，要开long long并且要用到快速幂和矩阵的线性逆元来求组合数

C++代码

#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 1e7 + 10 , MOD = 998244353;

int n , m , k;
int inv[N] , cm[N] , cn[N];
int qmi(int a , int b)      // 快速幂
{
    int res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void pre(int n , int m) // 预处理
{
    inv[0] = inv[1] = 1;
    for(int i = 2 ; i < N ; i ++)
        inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD;

    cm[0] = 1;
    for(int i = 1 ; i <= m ; i ++)
        cm[i] = (((cm[i - 1] * (m - i + 1)) % MOD) * inv[i]) % MOD;

    cn[0] = 1;
    for(int i = 1 ; i <= n ; i ++)
        cn[i] = (((cn[i - 1] * (n - i + 1)) % MOD) * inv[i]) % MOD;
}


signed main( )
{
    cin >> n >> m >> k;
    if(k == 0 || k == n * m) cout << 1 << '\n';
    else
    {
        pre(n , m);
        int ans = 0;
        for(int i = 0 ; i < m / 2 + (m % 2) ; i ++)
        {
            int t = (m - i) * n - k , b = m - 2 * i;
            if(t < 0 || t % b != 0 || t / b > n)
                continue;
            int y = t / b;
            ans = (ans + cm[i] * cn[y]) % MOD;
        }
        if(!(m & 1) && (n * m / 2) == k)
            ans = (ans + cm[m / 2] * qmi(2 , n - 1)) % MOD;
        cout << ans << '\n';
    }

    return 0;
}