Pagini recente » Cod sursa (job #2553306) | Cod sursa (job #785671) | Cod sursa (job #867277) | Cod sursa (job #1508417) | Cod sursa (job #1958702)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
const int kMaxDim = 55;
int n, m;
int mat[kMaxDim][kMaxDim], sum[kMaxDim][kMaxDim];
std::map< int64_t, int64_t > dp;
template< int N >
struct Pow {
static const int64_t pow = 51 * Pow< N-1 >::pow;
};
template<>
struct Pow< 0 > {
static const int64_t pow = 1;
};
inline int64_t Get(int top, int right, int bottom, int left, int corners) {
int64_t res = corners * Pow<0>::pow + top * Pow<1>::pow + right * Pow<2>::pow +
bottom * Pow<3>::pow + left * Pow<4>::pow;
return res;
}
void SolveRect(int top, int right, int bottom, int left, int corners) {
int onMargin = top + bottom + left + right;
for (int i = 0; i < 4; ++i)
if (corners & (1 << i))
++onMargin;
const int v[4] = {top, right, bottom, left};
int64_t goodSubs = 0;
for (int config = 0; config < 16; ++config) {
if ((config | corners) != corners)
continue;
int64_t curr = 1;
int conf = (config | ((config & 1) << 4));
for (int i = 0; i < 4; ++i) {
if ((conf & (1 << i)) || (conf & (1 << (i + 1))))
curr *= (1LL << v[i]);
else
curr *= (1LL << v[i]) - 1;
}
goodSubs += curr;
}
dp[Get(top, right, bottom, left, corners)] = (goodSubs << (50 - onMargin));
}
int main() {
std::ifstream inputFile("boundingbox.in");
std::ofstream outputFile("boundingbox.out");
for (int top = 0; top <= 48; ++top)
for (int bottom = 0; bottom <= 48; ++bottom)
for (int right = 0; right <= 48 && (right + 2) * (std::max(top, bottom) + 2) <= 50; ++right)
for (int left = 0; left <= 48 && (left + 2) * (std::max(top, bottom) + 2) <= 50; ++left)
for (int corners = 0; corners < 16; ++corners)
SolveRect(top, right, bottom, left, corners);
int testCount;
inputFile >> testCount;
while (testCount--) {
inputFile >> n >> m;
int oneCount = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
char ch;
inputFile >> ch;
mat[i][j] = ch - '0';
oneCount += mat[i][j];
sum[i][j] = sum[i][j - 1] + mat[i][j];
}
//one cell
int64_t res = oneCount * (1LL << (50 - oneCount));
//one line
for (int line = 1; line <= n; ++line) {
for (int col1 = 1; col1 <= m; ++col1) {
int inCount = mat[line][col1];
if (mat[line][col1]) {
for (int col2 = col1 + 1; col2 <= m; ++col2) {
inCount += mat[line][col2];
if (mat[line][col2])
res += (1LL << (50 - oneCount + (inCount - 2))) * (col2 - col1 + 1);
}
}
}
}
//one column
for (int col = 1; col <= m; ++col) {
for (int line1 = 1; line1 <= n; ++line1) {
int inCount = mat[line1][col];
if (mat[line1][col]) {
for (int line2 = line1 + 1; line2 <= n; ++line2) {
inCount += mat[line2][col];
if (mat[line2][col])
res += (1LL << (50 - oneCount + (inCount - 2))) * (line2 - line1 + 1);
}
}
}
}
//rectangle
for (int col1 = 1; col1 <= m; ++col1) {
for (int col2 = col1 + 1; col2 <= m; ++col2) {
for (int line1 = 1; line1 <= n; ++line1) {
int inCount = sum[line1][col2] - sum[line1][col1 - 1];
int top = sum[line1][col2 - 1] - sum[line1][col1];
int left = 0, right = 0;
for (int line2 = line1 + 1; line2 <= n; ++line2) {
inCount += sum[line2][col2] - sum[line2][col1 - 1];
int bottom = sum[line2][col2 - 1] - sum[line2][col1];
int outCount = oneCount - inCount;
int corners = (mat[line1][col1] << 0) + (mat[line1][col2] << 1) + (mat[line2][col2] << 2) + (mat[line2][col1] << 3);
int64_t aux = dp[Get(top, right, bottom, left, corners)] / (1LL << outCount);
aux = aux * (line2 - line1 + 1) * (col2 - col1 + 1);
res += aux;
left += mat[line2][col1];
right += mat[line2][col2];
}
}
}
}
int pow = 50;
while (res % 2 == 0 && pow && res) {
pow--;
res >>= 1;
}
if (res == 0)
pow = 0;
outputFile << res << '/' << (1LL << pow) << '\n';
}
inputFile.close();
outputFile.close();
return 0;
}
//Trust me, I'm the Doctor!