自动搬运

查看原文

来自洛谷，原作者为

	Hexarhy 干好饭，睡好觉，遇见好人。

搬运于2025-08-24 22:15:01，当前版本为作者最后更新于2020-11-18 21:50:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Preface

用 cmd 的引言：

OI 中的四类组合问题 : 判定问题，构造问题，极化问题，计数问题。 NOIP 命题风向 ： 弱化知识点，强化思维。

这题被 cmd 拿来作 NOIP 模拟赛 T2 了…… orz SWTR。

确实是一道计数好题，考察基本功和思维。

Solution

部分分参考出题人的题解。

将一次操作分解成一行一列来思考。不难发现一行被操作奇数次时才能改变状态。于是若有 $i$ 行 $j$ 列都被操作了奇数次，那么这次操作产生的答案就是：

$$\binom{n}{i}\binom{m}{j}$$

注意满足恰好总操作数等于 $k$ 的条件为：$0\le i,j\le k,i\equiv k\pmod2,j\equiv k\pmod2$。

那么枚举 $i,j$ ，不难得到总答案：

$$\sum_{i=0}^{\min\{n,k\}}\sum^{\min\{m,k\}}_{j=0}\binom{n}{i}\binom{m}{j}[i\equiv k\pmod 2][j\equiv k\pmod 2] $$

发现两个 $\sum$ 可以乘开，运用乘法分配律就有：

$$(\sum_{i=0}^{\min\{n,k\}}\binom{n}{i}[i\equiv k\pmod 2])\times(\sum^{\min\{m,k\}}_{j=0}\binom{m}{j}[j\equiv k\pmod 2]) $$

分别计算乘号两边，时间复杂度 $O(n)$。

然而不同的行列状态可能映射到同一个矩阵上，要减去这些重复的方案。

举个例子：

如果当前行/列状态为 $1$，那么是被操作了奇数次，$0$ 就是操作了偶数次。

下图 $i=2,j=2$。

行/列	1
1	0

下图 $i=0,j=0$。

行/列	0
0	0

两种合法的状态不同，但对应了同一个矩阵。再举例子发现，在 $(i,j)$ 合法的情况下，若 $(n-i),(m-j)\le k,(n-i)\equiv k\pmod 2,(m-j)\equiv k\pmod 2$，则 $(n-i,m-j)$ 也是一个合法的且重复的方案。

统计的时候计算出这些重复的，用总的减去重复的即可。

Notice

• 不可以在计算合法的时候对重复的方案 $/2$ ，因为在最后乘起来的时候会变成 $/4$，使得答案错误。（如果有误请指出，因为本人在写的时候踩了坑。）

• 注意合适的地方使用*1ll。

• 本题涉及到快速求模意义下组合数，预处理阶乘和逆元即可。不过值域略大，因此考虑用 $inv(i)$ 表示 $i!$ 的逆元，用费马小定理与快速幂即可求出。这一步的复杂度是 $O(n\log n)$，本题并不会超时。也可以线性做到 $O(n)$ 推出。

Code

本代码需要C++11。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
using namespace std;

template<typename tp>
void read(tp& a)
{
    register tp num=0;register int f=1;register char ch=getchar();
    while(!isdigit(ch) && ch!='-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    do
        num=num*10+int(ch-'0'),ch=getchar();
    while(isdigit(ch));
    a=num*f;
}
template<typename tp,typename...Args>
void read(tp& a,Args&...args){	read(a);read(args...);	}

typedef const int cint;
cint MOD=998244353;
cint MAXN=2e5+5;
int n,m,k;
int fact[MAXN],inv[MAXN];

int qpow(int base,int k)
{
    register int res=1;
    while(k)
    {
        if(k&1) res=1ll*res*base%MOD;
        base=1ll*base*base%MOD;
        k>>=1;
    }
    return res;
}

void calc(cint MAX)
{
    fact[0]=inv[0]=1;
    for(int i=1;i<=MAX;i++) fact[i]=1ll*fact[i-1]*i%MOD;
    for(int i=1;i<=MAX;i++) inv[i]=qpow(fact[i],MOD-2);
}

int C(cint n,cint m)
{
    return 1ll*fact[n]*inv[m]%MOD*inv[n-m]%MOD;
}

void solve(void)
{
    auto get=[&](cint l,cint r,cint N)
    {
        int res=0;
        for(int i=l;i<=r;i+=2)  res=(1ll*res+C(N,i))%MOD;
        return res;
    };
    int ans1=0,ans2=0,ans3=0,ans4=0;
    ans1=get(min(k,n)&1,min(k,n),n);
    ans2=get(min(k,m)&1,min(k,m),m);
    if(n%2==0 && m%2==0)
    {
        ans3=get(max(n-k,0),min(k,n),n);
        ans4=get(max(m-k,0),min(k,m),m);
    }
    printf("%lld\n",(1ll*ans1*ans2%MOD-1ll*ans3*ans4%MOD*inv[2]%MOD+MOD)%MOD);
}

int main()
{
    calc(2e5+2);
    int T;read(T);
    while(T--)
    {
        read(n,m,k);
        solve();
    }
    return 0;
}