Cod sursa(job #1231018)

Utilizator veleanduAlex Velea veleandu Data 19 septembrie 2014 14:13:46
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 4.27 kb
// toate fractiile din rez_dreptunghi au la numitor 50
// lucram cu numitorul 2^50 peste tot
// indiferent cate valori de 1 avem
#include <cassert>
#include <fstream>
#include <iostream>
#include <unordered_map>
using namespace std;

#define int64 long long

ifstream in("boundingbox.in");
ofstream out("boundingbox.out");

unordered_map<int, int64> rez_dreptunghi;

int el[50][50], sum[50][50];

inline int codif(int a, int b, int c, int d, int t) {
	return t * 51 * 51 * 51 * 51 + a * 51 * 51 * 51 + b * 51 * 51 + c * 51 + d; }

void solve_back(int a, int b, int c, int d, int t) {
	int64 nr_sol = 0;
 	int under_pow = a + b + c + d;   
	for (int i = 0; i < 4; ++i)
    	if (t & (1 << i))
			++under_pow;
	int x[4] = {a, b, c, d};

	for (int i = 0; i < 16; ++i)
		if ((i | t) == t) {
			int64 now = 1;
			int T = i | ((i & 1) << 4);
			for (int p = 0; p < 4; ++p) {
				if ((T & (1 << p)) or (T & (1 << (p + 1))))
					now *= 1LL << x[p];
				else
					now *= (1LL << x[p]) - 1;
			}
			nr_sol += now;
		}
	nr_sol <<= (50 - under_pow);
//	cerr << 1.0 * nr_sol / (1LL << 50) << '\n';
	rez_dreptunghi[codif(a, b, c, d, t)] = nr_sol;
}

int main() {
//	solve_back(0, 0, 0, 0, 10);
//	return 0;
	for (int sta = 0; sta <= 48; ++sta)
		for (int stb = 0; stb <= 48; ++stb)
			for (int dra = 0; dra <= 48 and (dra + 2) * (max(sta, stb) + 2) <= 50; ++dra)
				for (int drb = 0; (drb + 2) * (max(sta, stb) + 2) <= 50; ++drb) {
					for (int t = 0; t < 16; ++t) {
/*						if (rez_dreptunghi[codif(sta, dra, stb, drb, t)] == 1)
							assert(0);
                        rez_dreptunghi[codif(sta, dra, stb, drb, t)] = 1;
						doar ca se ne asiguram ca hashuirea e unica
*/
 						solve_back(sta, dra, stb, drb, t);
					}
				}
//	cerr << rez_dreptunghi[codif(0, 0, 0, 0, 10)] / (1LL << 46) << '\n';
	int t;
	in >> t;
	while (t--) {
		int n, m, total = 0;
		in >> n >> m;
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
				char c;
				in >> c;
				el[i][j] = c - '0';
				total += el[i][j];
			}

		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				sum[i][j] = sum[i][j - 1] + el[i][j];
		assert(total <= 50);
	   	int64 rez = 1LL * total * ((1LL << (50 - total)));
// 		cerr << 1.0 * (rez >> 46LL) / 16.0 << "!!!!!!!!!\n\n";    	
		for (int c1 = 1; c1 <= m; ++c1)
			for (int c2 = c1 + 1; c2 <= m; ++c2) {
				for (int l1 = 1; l1 < n; ++l1) {
					int inside = sum[l1][c2] - sum[l1][c1 - 1];
					int top = sum[l1][c2 - 1] - sum[l1][c1];
					int b1 = 0, b2 = 0;
					for (int l2 = l1 + 1; l2 <= n; ++l2) {
						inside += sum[l2][c2] - sum[l2][c1 - 1];
						int bottom = sum[l2][c2 - 1] - sum[l2][c1];
						int outside = total - inside;
                        int T = el[l2][c1] + el[l1][c1] * 2 + el[l1][c2] * 4 + el[l2][c2] * 8;
//						cerr << c1 << ' ' << c2 << '\n';
//						cerr << b1 << ' ' << top << ' ' << b2 << ' ' << bottom << ' ' << T << '\n';
//						cerr << (1.0 * (rez_dreptunghi[codif(b1, top, b2, bottom, T)] >> 46LL) / 16) * (l2 - l1 + 1) * (c2 - c1 + 1) / (1 << outside) << '\n';
                        assert(outside >= 0);
						rez += (rez_dreptunghi[codif(b1, top, b2, bottom, T)] >> outside) * (l2 - l1 + 1) * (c2 - c1 + 1);

//						cerr << 1.0 * (rez >> 46LL) / 16.0 << "\n\n";

                        b1 += el[l2][c1];
						b2 += el[l2][c2];
					}
				}
			}
//		cerr << 1.0 * (rez >> 46LL) / 16.0 << "\n\n";
 
		for (int i = 1; i <= n; ++i)
			for (int c1 = 1; c1 <= m; ++c1)
				for (int c2 = c1 + 1; c2 <= m; ++c2) {
					if (el[i][c1] == 1 and el[i][c2] == 1) {
						assert( (50 - (total - (sum[i][c2 - 1] - sum[i][c1]))) >= 0);
						rez += (1LL << (50 - (total - (sum[i][c2 - 1] - sum[i][c1])))) * 1LL * (c2 - c1 + 1);
					}
				}
// 		cerr << 1.0 * (rez >> 46LL) / 16.0 << "\n\n";
		for (int c = 1; c <= m; ++c)
			for (int l1 = 1; l1 <= n; ++l1) {
				int inside = el[l1][c];
				for (int l2 = l1 + 1; l2 <= n; ++l2) {
					inside += el[l2][c];
					if (el[l1][c] == 1 and el[l2][c] == 1) {
						assert( (50 - (total - (inside - 2))) >= 0);
						rez += (1LL << (50 - (total - (inside - 2)))) * (l2 - l1 + 1);
					}
				}
			}
//  		cerr << 1.0 * (rez >> 46LL) / 16.0 << "\n\n";
		int p = 50;
		assert(rez >= 0);
		while ((rez % 2 == 0) and rez != 0 and p > 0) {
			p--;
			rez /= 2;
		}

		if (rez == 0)
			p = 0;
		assert(p >= 0);
        out << rez << '/' << (1LL << p) << '\n';
	}
	return 0;
}