题解 | 矩形计数

#include <iostream>
//#include<algorithm>
//#include<cmath>
#include<iostream> 
using namespace std;

typedef long long ll;

ll p = 1000000007;

ll fast_pow_mod(ll base, ll exp, ll p) {
	if (base == 0) return 0;
	ll ans = 1;
	while (exp > 0) {
		if(exp & 1) ans = (ans * base) % p;
		base = (base * base) % p;
		exp >>= 1;
	}
	return ans;
}

int main() {
	int n, m;
//	string s;
	cin >> n >> m;
//	int p1 = 0, p2 = 0;
	ll ans = 0;
	int len = 0;
//	bool flag = false;
	int a[n + 1][m +1];
//	for (int i = 0; i < n; i++) {
//		for(int j = 0; j < m; j++) {
//			cin >> a[i][j];
//			if (j > 0 && a[i][j] != a[i][j - 1]) {
//				//结算
//				ans = (ans + len * (len + 1) / 2) % p;
//				len = 1; 
//			} else {
//				len++;
//			}
//		}
//		ans = (ans + len * (len + 1) / 2) % p;
//		len = 0; 
//	}
//	for (int j = 0; j < m; j++) {
//		for(int i = 0; i < n; i++) {
////			cin >> a[i][j]
//			if (i > 0 && a[i][j] != a[i - 1][j]) {
//				//结算
//				ans = (ans + len * (len + 1) / 2) % p;
//				len = 1; 
//			} else {
//				len++;
//			}
//		}
//		ans = (ans + len * (len + 1) / 2) % p;
//		len = 0; 
//	}
//	ll e = n * m;
//	ans = ans - e % p;
//	cout << (ans >= 0 ? ans : ans + p) << endl;

	for (int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> a[i][j];
			len += a[i][j];
		}
		ll tmp = (ans + fast_pow_mod(2, len, p) + fast_pow_mod(2, m - len, p)) % p - 2;
		ans = tmp + (tmp >= 0 ? 0 : p);
		len = 0; 
	}
	for (int j = 0; j < m; j++) {
		for(int i = 0; i < n; i++) {
//			cin >> a[i][j];
			len += a[i][j];
		}
		ll tmp = (ans + fast_pow_mod(2, len, p) + fast_pow_mod(2, n - len, p)) % p - 2;
		ans = tmp + (tmp >= 0 ? 0 : p);
		len = 0; 
	}
	ans = ans - (n * m % p);
	cout << (ans >= 0 ? ans : ans + p) << endl;
}