#P3381. 第3题-网格元素反置
-
1000ms
Tried: 4
Accepted: 2
Difficulty: 8
所属公司 :
科大讯飞
时间 :2025年8月16日
-
算法标签>数论
第3题-网格元素反置
思路
-
行列独立翻转为异或模型:最终单元 ai,j=ri⊕cj,其中 ri 为第 i 行翻转奇偶,cj 为第 j 列翻转奇偶。只需记录被翻转奇数次的行集合 R 与列集合 C,其大小分别为 ∣R∣ 与 ∣C∣。
-
每一行只有两种形态:
-
若该行未翻(ri=0),则该行的二进制数为 V0,其中
- V0=∑j∈C2m−j modMOD;
-
若该行被翻(ri=1),该行即为按位取反的 V1,其中
- V1=(2m−1−V0) modMOD。
-
-
整体按行拼接是等比的移位求和:
-
记一行的位长为 m。第 i 行(从 1 到 n)处在从高到低第 n−i 个区块,其权为 2m⋅(n−i)。
-
定义
-
-
则总答案
-
-
等比数列求和:
- 令 q=2mmodMOD。若 q=1,则 Sall=q−1qn−1modMOD;若 q=1,则 Sall=nmodMOD。
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 ,我们使用 ai,j 表示网格中从上往下数第 i 行和从左往右数第 j 列的单元格,初始所有单元格中的数字都为 0 ,Tk将进行 k 次操作,每次操作两个值 x,y :
-
当 x=1 时,将第 y 列的所有元素反置。
-
当 x=2 时,将第 y 行的所有元素反置。
所有操作结束后 Tk 将会按照
a1,1,a1,2,...,a1,m,a2,1,a2,2,...,a2,m,...,an−1,1,an−1,2,...,an−1,m,an,1,an,2,...,an,m
的顺序依次拼接形成一个二进制数字,Tk 想知道这个二进制数字对应的十进制为多少,输出这个十进制数字(不带前导零),由于答案可能很大,你只需输出对 109+7 取模后的结果即可。
【反置】若当前数字为 0 ,反置后为 1 ;若当前字符为 1 ,反置后为 0 。
输入描述
第一行输入三个整数 n,m,k(1≦n,m≦109,1≦k≦2×105) 表示网格大小以及 Tk 的操作次数。
接下来 k 行每一行输入两个整数 x,y(x∈ {1,2} ,当 x=1 时 1≦y≦m , 当 x=2 时 1≦y≦n) 表示 Tk 的操作。
输出描述
输出一个整数表示拼接形成二进制对应十进制对 109+7 取模的结果。
样例1
输入
5 5 4
1 2
2 5
1 3
2 2
输出
13218195


