Pagini recente » Cod sursa (job #417391) | Cod sursa (job #538720) | Cod sursa (job #3158558) | Cod sursa (job #529801) | Cod sursa (job #1478919)
#include <iostream>
#include <cstring>
#define lint long long int
using namespace std;
inline lint gcd (lint a, lint b) {
if (!b)
return a;
lint r = a % b;
while (r) {
a = b;
b = r;
r = a % b;
}
return b;
}
const int NMAX = 55;
int r, c;
char mat[NMAX][NMAX];
int s_part[NMAX][NMAX];
inline void get_precalc() {
int j;
for (int i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j)
s_part[i][j] = (mat[i][j] == '1') + s_part[i][j - 1] + s_part[i - 1][j] - s_part[i - 1][j - 1];
}
inline int first_lines (int lin) {
return s_part[lin][c];
}
inline int last_lines (int lin) {
return s_part[r][c] - s_part[lin - 1][c];
}
inline int first_cols (int col) {
return s_part[r][col];
}
inline int last_cols (int col) {
return s_part[r][c] - s_part[r][col - 1];
}
inline int lower_left (int lin, int col) {
return s_part[lin][col];
}
inline int lower_right (int lin, int col) {
return s_part[lin][c] - s_part[lin][col - 1];
}
inline int upper_left (int lin, int col) {
return s_part[r][col] - s_part[lin - 1][col];
}
inline int upper_right (int lin, int col) {
return s_part[r][c] - s_part[r][col - 1] - s_part[lin - 1][c] + s_part[lin - 1][col - 1];
}
lint pow2[55];
inline void precalc_pow2 () {
pow2[0] = 1;
for (int i = 1; i <= 54; ++ i)
pow2[i] = 2 * pow2[i - 1];
}
int main()
{
precalc_pow2();
int t = 0;
cin >> t;
while (t --) {
cin >> r >> c;
for (int i = 1; i <= r; ++ i) {
cin.get();
cin.get(mat[i] + 1, NMAX);
}
get_precalc();
int ones = 0;
int i, j;
for (i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j)
ones += (mat[i][j] == '1');
//cout << "ones = " << ones << endl;
lint ans = 0;
lint here = 0;
for (i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j) {
here = pow2[ones];
here -= (pow2[first_lines(i - 1)] - 1);
// cout << "sus " << first_lines(i - 1) << endl;
here -= (pow2[last_lines(i + 1)] - 1);
// cout << "jos " << last_lines(i + 1) << endl;
here -= (pow2[first_cols(j - 1)] - 1);
// cout << "stanga " << first_cols(j - 1) << endl;
here -= (pow2[last_cols(j + 1)] - 1);
// cout << "dreapta " << last_cols(j + 1) << endl;
here += (pow2[lower_left(i - 1, j - 1)] - 1);
// cout << "stanga jos " << lower_left(i - 1, j - 1) << endl;
here += (pow2[lower_right(i - 1, j + 1)] - 1);
// cout << "dreapta jos " << lower_right(i - 1, j + 1) << endl;
here += (pow2[upper_left(i + 1, j - 1)] - 1);
// cout << "stanga sus " << upper_left(i + 1, j - 1) << endl;
here += (pow2[upper_right(i + 1, j + 1)] - 1);
// cout << "dreapta sus " << upper_right(i + 1, j + 1) << endl;
here --;
//cout << i << ' ' << j << ' ' << here << endl;
ans += here;
}
lint d = gcd(ans, pow2[ones]);
cout << ans / d << '/' << pow2[ones] / d << '\n';
}
return 0;
}