题解

题目描述

给定一个 $n$ 行 $m$ 列的二元网格（每个格子值为 $0$ 或 $1$），用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。允许的操作是任意次选择两个相邻格子（上下或左右）并交换它们的值。定义格子的权值为该格子与相邻格子中数值不同的个数，网格的奇偶性为所有格子权值之和的奇偶性。给定初始网格，问在经过任意次上述操作后，能够得到多少种不同的偶网格（即权值和为偶数的网格）的配置数。结果对 $10^9+7$ 取模。

思路

1. 可达状态分析
   网格连通且只允许相邻格子交换，交换操作可在连通图上生成对所有格子值的任意排列。因此，所有与初始网格拥有相同的 $1$ 的个数 $k$ 的二元矩阵均可达到。

2. 奇偶性分析

   • 某格子权值为与其相邻且数值不同的格子个数。
   • 所有格子权值之和等于所有相邻格子对中数值不同的对数乘以 $2$（每条边对应两个端点各统计一次）。
   • 因此，总权值和 $=2\times E$，其中 $E$ 为相异的相邻对数。$2E$ 恒为偶数。
   • 所以任意二元矩阵的权值和均为偶数，所有可达矩阵都是偶网格。

3. 组合计数

   • 可达的偶网格数即为所有具有 $k$ 个 $1$ 的二元矩阵数目：$$\binom{nm}{k}$$
   • 其中 $nm$ 为格子总数，$k=\sum_{i,j} a_{i,j}$。

4. 取模计算

   • 预处理阶乘 $\mathrm{fac}[i]=i!\bmod(10^9+7)$ 及逆元 $\mathrm{inv}[i]=(i!)^{-1}\bmod(10^9+7)$，时间 $O(nm)$。
   • 最终结果 $=\mathrm{fac}[nm]$$\times$$\mathrm{inv}[k]$$\times$$\mathrm{inv}[nm-k]$$\bmod(10^9+7)$。

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

// 快速幂取模
long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int N = n * m;
    int k = 0;
    // 统计初始网格中 1 的个数
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x == 1) k++;
    }

    // 预处理阶乘及逆阶乘
    vector<long long> fac(N + 1), inv(N + 1);
    fac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
    // 利用费马小定理求逆阶乘
    inv[N] = modpow(fac[N], MOD - 2);
    for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;

    // 计算组合数 C(N, k)
    long long ans = fac[N] * inv[k] % MOD * inv[N - k] % MOD;
    cout << ans << "\n";
    return 0;
}

Python

#!/usr/bin/env python3
import sys
MOD = 10**9 + 7
def modpow(a: int, e: int) -> int:
    """Fast exponentiation a^e % MOD."""
    r = 1
    a %= MOD
    while e:
        if e & 1:
            r = r * a % MOD
        a = a * a % MOD
        e >>= 1
    return r
def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    N = n * m
    k = sum(1 for _ in range(N) if next(it) == '1')
    fac = [1] * (N + 1)
    inv = [1] * (N + 1)
    for i in range(1, N + 1):
        fac[i] = fac[i - 1] * i % MOD
    inv[N] = pow(fac[N], MOD - 2, MOD)
    for i in range(N, 0, -1):
        inv[i - 1] = inv[i] * i % MOD
    ans = fac[N] * inv[k] % MOD * inv[N - k] % MOD
    print(ans)
if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1_000_000_007;

   
    static long modpow(long a, long e) {
        long r = 1;
        a %= MOD;
        while (e > 0) {
            if ((e & 1) == 1) r = r * a % MOD;
            a = a * a % MOD;
            e >>= 1;
        }
        return r;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); }
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String line = br.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }
        int nextInt() throws IOException { return Integer.parseInt(next()); }
    }

    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader();
        int n = in.nextInt();
        int m = in.nextInt();
        int N = n * m;
        int k = 0;
        for (int i = 0; i < N; i++) {
            if (in.nextInt() == 1) k++;
        }
        long[] fac = new long[N + 1];
        long[] inv = new long[N + 1];
        fac[0] = 1;
        for (int i = 1; i <= N; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }
        inv[N] = modpow(fac[N], MOD - 2);
        for (int i = N; i > 0; i--) {
            inv[i - 1] = inv[i] * i % MOD;
        }
        long ans = fac[N] * inv[k] % MOD * inv[N - k] % MOD;
        System.out.println(ans);
    }
}

题目内容

有一个 $n$ 行 $m$ 列的网格，我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。每个方格的值为 $0$ 或 $1$ ，且任何操作均不得超出网格边界。

我们定义单元格的权值为该单元格与其相邻且数值不同的单元格个数。网格的奇偶性为所有单元格权值之和的奇偶性。

$Tk$ 可以任意次进行如下操作：

• 选择两个相邻的单元格交换它们的值.

Tk 想知道经过任意次操作后，能够得到多少种不同的网格为偶网格.

在这里，当$|x-x'|+|y-y'|=1$ 时，单元格 $(x,y)$ 与 $(x,y)$ 被认为是相邻的.

我们认为若两个网格至少存在一个相同位置的单元格数值不同，则认为这两个网格不同.

由于答案可能很大，请将答案对 $10^9+7$ 取模后输出.

输入描述

第一行输入两个整数 $n,m (2 ≤n,m,n×m ≤5×10^5)$ ，表示网格的行数和列数.

接下来输入 $n$ 行，每行 $m$ 个整数 $a_i,j(a_i,j∈$ {$0,1$}$)$，表示初始时每个单元格的值.

输出描述

输出一个整数，表示不同偶矩阵的数量.

由于答案可能很大，请将答案对 $10^9+7$ 取模后输出

样例1

输入

2 2
1 0
0 1

输出

6

说明

下面给出这 $6$ 种不同偶矩阵的方案：