Pagini recente » Cod sursa (job #224035) | Cod sursa (job #934861) | Cod sursa (job #1934842) | Cod sursa (job #2500433) | Cod sursa (job #1230666)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 7;
ll gcd(ll a, ll b) {
if(!b)
return a;
return gcd(b, a % b);
}
vector<vector<int>> sum;
int getSum(int x0, int y0, int x1, int y1) {
if(x1 < x0 || y1 < y0)
return 0;
int ans = sum[x1][y1];
if(x0 - 1 >= 0)
ans -= sum[x0 - 1][y1];
if(y0 - 1 >= 0)
ans -= sum[x1][y0 - 1];
if(x0 - 1 >= 0 && y0 - 1 >= 0)
ans += sum[x0 - 1][y0 - 1];
return ans;
}
int main() {
#ifdef INFOARENA
ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");
#endif
//ifstream cin("test.in");
int t; cin >> t;
while(t--) {
int n, m; cin >> n >> m;
vector<string> A(n);
ll all = 1;
sum = vector<vector<int>> (n, vector<int> (m, 0));
int blacks = 0;
for(int i = 0; i < n; ++i) {
cin >> A[i];
for(int j = 0; j < m; ++j) {
if(A[i][j] == '1') {
all *= 2;
sum[i][j]++;
blacks++;
}
if(i - 1 >= 0)
sum[i][j] += sum[i - 1][j];
if(j - 1 >= 0)
sum[i][j] += sum[i][j - 1];
if(i - 1 >= 0&& j - 1 >= 0)
sum[i][j] -= sum[i - 1][j - 1];
}
}
vector<int> x(2, 0), y(2, 0);
ll good = 0;
for(x[0] = 0; x[0] < n; ++x[0])
for(y[0] = 0; y[0] < m; ++y[0])
for(x[1] = x[0] + 1; x[1] < n; ++x[1])
for(y[1] = y[0] + 1; y[1] < m; ++y[1]) {
ll coef = (1LL << getSum(x[0] + 1, y[0] + 1, x[1] - 1, y[1] - 1));
//cerr << coef << "\n";
vector<int> SL(2, 0), SC(2, 0);
SL[0] = getSum(x[0], y[0] + 1, x[0], y[1] - 1);
SL[1] = getSum(x[1], y[0] + 1, x[1], y[1] - 1);
SC[0] = getSum(x[0] + 1, y[0], x[1] - 1, y[0]);
SC[1] = getSum(x[0] + 1, y[1], x[1] - 1, y[1]);
for(int mask = 0; mask < 16; ++mask) {
bool ok = true;
vector<int> hasL(2, 0), hasC(2, 0);
for(int i = 0; i < 4; ++i)
if((1 << i) & mask) {
if(A[i & 1][(i >> 1) & 1] == '0')
ok = false;
else
hasL[i & 1] = 1, hasC[(i >> 1) & 1] = 1;
}
if(ok == false)
continue;
ll now = 1;
for(int i = 0; i < 2; ++i) {
if(hasL[i] == 0)
now *= SL[i];
if(hasC[i] == 0)
now *= SC[i];
}
good += now * coef * (x[1] - x[0] + 1) * (y[1] - y[0] + 1);
}
}
for(int line = 0; line < n; ++line)
for(int i = 0; i < m; ++i)
for(int j = i; j < m; ++j) {
if(A[line][i] != '1' || A[line][j] != '1')
continue;
good += (j - i + 1) * (1LL << getSum(line, i + 1, line, j - 1));
}
for(int col = 0; col < m; ++col)
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j) {
if(A[i][col] != '1' || A[j][col] != '1')
continue;
good += (j - i + 1) * (1LL << getSum(i + 1, col, j - 1, col));
}
ll g = gcd(good, all);
good /= g, all /= g;
cout << good << "/" << all << "\n";
}
}