思路

• 行列独立翻转为异或模型：最终单元 $a_{i,j} = r_i \oplus c_j$，其中 $r_i$ 为第 $i$ 行翻转奇偶，$c_j$ 为第 $j$ 列翻转奇偶。只需记录被翻转奇数次的行集合 $R$ 与列集合 $C$，其大小分别为 $|R|$ 与 $|C|$。

• 每一行只有两种形态：

  • 若该行未翻（$r_i=0$），则该行的二进制数为 $V_0$，其中

    • $V_0=\sum_{j\in C} 2^{m-j}\ \bmod MOD$；

  • 若该行被翻（$r_i=1$），该行即为按位取反的 $V_1$，其中

    • $V_1=(2^m-1 - V_0)\ \bmod MOD$。

• 整体按行拼接是等比的移位求和：

  • 记一行的位长为 $m$。第 $i$ 行（从 $1$ 到 $n$）处在从高到低第 $n-i$ 个区块，其权为 $2^{m\cdot (n-i)}$。

  • 定义

    • 

    • 

  • 则总答案

    • 

• 等比数列求和：

  • 令 $q=2^m \bmod MOD$。若 $q\neq 1$，则 $S_{\text{all}}=\dfrac{q^n-1}{q-1}\bmod MOD$；若 $q=1$，则 $S_{\text{all}}=n \bmod MOD$。

C++

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

// 快速幂：计算 a^e % MOD，e 可能很大
long long mod_pow(long long a, unsigned long long e) {
	long long res = 1 % MOD;
	a %= MOD;
	while (e > 0) {
		if (e & 1ULL) res = (__int128)res * a % MOD;
		a = (__int128)a * a % MOD;
		e >>= 1ULL;
	}
	return res;
}

// 费马小定理求逆元：x^{-1} = x^{MOD-2} (MOD 为质数)
long long mod_inv(long long x) {
	return mod_pow((x % MOD + MOD) % MOD, MOD - 2);
}

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

	long long n, m;
	int k;
	if (!(cin >> n >> m >> k)) return 0;

	// R 存储被奇数次翻转的行下标集合；C 存储被奇数次翻转的列下标集合
	unordered_set<long long> R, C;
	R.reserve(k * 2);
	C.reserve(k * 2);

	// 读入并做“出现即加入、再次出现即删除”的奇偶翻转
	for (int t = 0; t < k; ++t) {
		int x;
		long long y;
		cin >> x >> y;
		if (x == 1) {
			if (C.count(y)) C.erase(y);
			else C.insert(y);
		} else {
			if (R.count(y)) R.erase(y);
			else R.insert(y);
		}
	}

	// 计算 V0 = sum_{j in C} 2^{m-j}，表示“该行未翻转时”的二进制值
	long long V0 = 0;
	for (auto j : C) {
		unsigned long long exp = (unsigned long long)(m - j);
		long long add = mod_pow(2, exp);
		V0 += add;
		if (V0 >= MOD) V0 -= MOD;
	}

	// 2^m
	long long pow2m = mod_pow(2, (unsigned long long)m);

	// V1 = (2^m - 1 - V0)，表示“该行翻转时”的二进制值（m 位按位取反）
	long long V1 = (pow2m - 1 - V0) % MOD;
	if (V1 < 0) V1 += MOD;

	// 按行拼接的权值公比 q = 2^m
	long long q = pow2m;

	// S_all = sum_{t=0}^{n-1} q^t，等比数列求和，q==1 特判
	long long S_all;
	if (q == 1) {
		S_all = n % MOD;
	} else {
		long long qn = mod_pow(q, (unsigned long long)n);
		long long numerator = (qn - 1) % MOD;
		if (numerator < 0) numerator += MOD;
		long long denom = (q - 1 + MOD) % MOD;
		S_all = (__int128)numerator * mod_inv(denom) % MOD;
	}

	// S_R = sum_{i in R} 2^{m*(n-i)}，即被翻转行在整体中的权值之和
	long long S_R = 0;
	for (auto i : R) {
		unsigned long long d = (unsigned long long)(n - i);
		unsigned long long exp = (unsigned long long)m * d; // 指数可能达到 1e18
		long long add = mod_pow(2, exp);
		S_R += add;
		if (S_R >= MOD) S_R -= MOD;
	}

	// 未翻转行的总权值
	long long S_not = (S_all - S_R) % MOD;
	if (S_not < 0) S_not += MOD;

	// 答案：未翻转行贡献 V0*S_not，翻转行贡献 V1*S_R
	long long ans = ( ( (__int128)V0 * S_not ) + ( (__int128)V1 * S_R ) ) % MOD;
	if (ans < 0) ans += MOD;

	cout << ans << '\n';
	return 0;
}

Python

import sys

MOD = 10**9 + 7

# 快速幂：计算 a^e % MOD
def mod_pow(a: int, e: int) -> int:
	res = 1
	a %= MOD
	while e > 0:
		if e & 1:
			res = (res * a) % MOD
		a = (a * a) % MOD
		e >>= 1
	return res

# 费马小定理求逆元
def mod_inv(x: int) -> int:
	return mod_pow(x % MOD, MOD - 2)

def main():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it)); m = int(next(it)); k = int(next(it))

	# R：被奇数次翻转的行；C：被奇数次翻转的列
	R = set()
	C = set()

	# 读操作并用集合维护“奇偶翻转”
	for _ in range(k):
		x = int(next(it)); y = int(next(it))
		if x == 1:
			if y in C: C.remove(y)
			else: C.add(y)
		else:
			if y in R: R.remove(y)
			else: R.add(y)

	# V0 = sum_{j in C} 2^{m-j}，行未翻转时的二进制值
	V0 = 0
	for j in C:
		exp = m - j
		add = mod_pow(2, exp)
		V0 = (V0 + add) % MOD

	# 2^m 与 V1（行翻转时的二进制值）
	pow2m = mod_pow(2, m)
	V1 = (pow2m - 1 - V0) % MOD

	# 等比数列的公比 q = 2^m
	q = pow2m
	if q == 1:
		S_all = n % MOD
	else:
		qn = mod_pow(q, n)
		S_all = ((qn - 1) % MOD) * mod_inv((q - 1) % MOD) % MOD

	# S_R = 被翻转行的权值之和
	S_R = 0
	for i in R:
		d = n - i
		exp = m * d  # 可能达到 1e18
		add = mod_pow(2, exp)
		S_R = (S_R + add) % MOD

	# 未翻转行权值
	S_not = (S_all - S_R) % MOD

	# 总答案
	ans = ( (V0 * S_not) + (V1 * S_R) ) % MOD
	print(ans)

if __name__ == "__main__":
	main()

Java

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

public class Main {
	static final long MOD = 1_000_000_007L;

	// 快速幂：计算 a^e % MOD
	static long modPow(long a, long e) {
		a %= MOD;
		long res = 1 % MOD;
		while (e > 0) {
			if ((e & 1L) == 1L) res = (res * a) % MOD;
			a = (a * a) % MOD;
			e >>= 1;
		}
		return res;
	}

	// 费马小定理求逆元
	static long modInv(long x) {
		x %= MOD;
		if (x < 0) x += MOD;
		return modPow(x, MOD - 2);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		// R：被奇数次翻转的行；C：被奇数次翻转的列
		HashSet<Long> R = new HashSet<>(k * 2);
		HashSet<Long> C = new HashSet<>(k * 2);

		// 读入操作并做奇偶翻转
		for (int t = 0; t < k; t++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			if (x == 1) {
				if (C.contains(y)) C.remove(y);
				else C.add(y);
			} else {
				if (R.contains(y)) R.remove(y);
				else R.add(y);
			}
		}

		// V0 = sum_{j in C} 2^{m-j}
		long V0 = 0;
		for (long j : C) {
			long exp = m - j;              // 指数非负
			long add = modPow(2, exp);
			V0 += add;
			if (V0 >= MOD) V0 -= MOD;
		}

		// 2^m 与 V1（行翻转时的数值）
		long pow2m = modPow(2, m);
		long V1 = (pow2m - 1 - V0) % MOD;
		if (V1 < 0) V1 += MOD;

		// 等比数列公比 q = 2^m
		long q = pow2m;
		long S_all;
		if (q == 1) {
			S_all = n % MOD;
		} else {
			long qn = modPow(q, n);
			long numerator = (qn - 1) % MOD;
			if (numerator < 0) numerator += MOD;
			long denom = (q - 1 + MOD) % MOD;
			S_all = (numerator * modInv(denom)) % MOD;
		}

		// S_R = 被翻转行整体权值之和
		long S_R = 0;
		for (long i : R) {
			long d = n - i;
			long exp = m * d;              // 可能达到 1e18，long 可承载
			long add = modPow(2, exp);
			S_R += add;
			if (S_R >= MOD) S_R -= MOD;
		}

		// 未翻转行权值
		long S_not = (S_all - S_R) % MOD;
		if (S_not < 0) S_not += MOD;

		// 总答案
		long ans = ( ( (V0 * S_not) % MOD ) + ( (V1 * S_R) % MOD ) ) % MOD;
		if (ans < 0) ans += MOD;

		System.out.println(ans);
	}
}

题目内容

有一个 $n$ 行 $m$ 列的网格 $a$ ，我们使用 $a_{i,j}$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格，初始所有单元格中的数字都为 $0$ ，Tk将进行 $k$ 次操作，每次操作两个值 $x,y$ ：

• 当 $x=1$ 时，将第 $y$ 列的所有元素反置。

• 当 $x=2$ 时，将第 $y$ 行的所有元素反置。

所有操作结束后 Tk 将会按照

$a_{1,1},a_{1,2},...,$$a_{1,m},a_{2,1},a_{2,2},...,$$a_{2,m},...,a_{n-1,1},a_{n-1,2},...,$$a_{n-1,m},a_{n,1},$$a_{n,2},...,a_{n,m}$

的顺序依次拼接形成一个二进制数字，Tk 想知道这个二进制数字对应的十进制为多少，输出这个十进制数字(不带前导零)，由于答案可能很大，你只需输出对 $10^9+7$ 取模后的结果即可。

【反置】若当前数字为 $0$ ，反置后为 $1$ ；若当前字符为 $1$ ，反置后为 $0$ 。

输入描述

第一行输入三个整数 $n,m,k(1≦n,m≦10^9,1≦k≦2×10^5)$ 表示网格大小以及 Tk 的操作次数。

接下来 $k$ 行每一行输入两个整数 $x,y(x∈$ {$1,2$} ，当 $x=1$ 时 $1≦y≦m$ ， 当 $x=2$ 时 $1≦y≦n)$ 表示 Tk 的操作。

输出描述

输出一个整数表示拼接形成二进制对应十进制对 $10^9+7$ 取模的结果。

样例1

输入

5 5 4
1 2
2 5
1 3
2 2

输出

13218195