# Cod sursa(job #1862465)

Utilizator Data 29 ianuarie 2017 22:58:39 Boundingbox 100 cpp done Arhiva de probleme 3.87 kb
``````#include <fstream>
using namespace std;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
int N, M;
long long Matrix[55][55];
long long Partial[55][55];
long long Power[55];
long long L[55][55], C[55][55];
int la[5], c[5];
long long res, ans;
int x[5];
bool Use[5];
long long p = 1;
void precalcPower()
{
Power[0] = 1;
for(int i = 1; i <= 50; i++)
Power[i] = Power[i - 1] * 2;
}
{
f >> N >> M;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
char ch;
f >> ch;
Matrix[i][j] = ch - '0';
Partial[i][j] = Partial[i - 1][j] + Partial[i][j - 1] - Partial[i - 1][j - 1] + Matrix[i][j];
L[i][j] = L[i][j - 1] + Matrix[i][j];
C[i][j] = C[i - 1][j] + Matrix[i][j];
}
}

inline long long nb1(int i1, int j1, int i2, int j2)
{
if(i1 > i2 || j1 > j2)
return 0;
return Partial[i2][j2] - Partial[i1 - 1][j2] - Partial[i2][j1 - 1] + Partial[i1 - 1][j1 - 1];
}
void back(int k)
{
for(int i = x[k - 1] + 1; i <= 4; i++)
{
if(c[i] == 0)
continue;
x[k] = i;
Use[i] = 1;
long long aux = 1;
for(int p = 1; p <= 4; p++)
{
int next = p + 1;
if(next == 5)
next = 1;
if(Use[p] == 1 || Use[next] == 1)
aux *= Power[la[p]];
else
aux *= (Power[la[p]] - 1);
}
ans += aux;
if(k < 4)
back(k + 1);
Use[i] = 0;
}
}
void Solve()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
for(int k = i + 1; k <= N; k++)
{
int ind = 0;
for(int l = j + 1; l <= M; l++)
{
Use[1] = Use[2] = Use[3] = Use[4] = 0;
la[1] = L[i][l - 1] - L[i][j];
la[2] = C[k - 1][l] - C[i][l];
la[3] = L[k][l - 1] - L[k][j];
la[4] = C[k - 1][j] - C[i][j];
p = (Power[la[1]] - 1) * (Power[la[2]] - 1) * (Power[la[3]] - 1) * (Power[la[4]] - 1);
c[1] = Matrix[i][j];
c[2] = Matrix[i][l];
c[3] = Matrix[k][l];
c[4] = Matrix[k][j];
ans = 0;
back(1);
ans += p;
res += 1LL * (l - j + 1) * (k - i + 1) * ans * (Power[nb1(i + 1, j + 1, k - 1, l - 1)]);
}

}
}
}

void Solve2()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
if(Matrix[i][j] == 0)
continue;
for(int k = j + 1; k <= M; k++)
{
if(Matrix[i][k] == 0)
continue;
res += Power[(L[i][k - 1] - L[i][j])] * (k - j + 1);
}
}
for(int i = 1; i <= M; i++)
for(int j = 1; j <= N; j++)
{
if(Matrix[j][i] == 0)
continue;
for(int k = j + 1; k <= N; k++)
{
if(Matrix[k][i] == 0)
continue;
res += Power[(C[k - 1][i] - C[j][i])] * (k - j + 1);
}

}
}
long long CMMDC(long long a, long long b)
{
long long r = a % b;
while(r != 0)
{
a = b;
b = r;
r = a % b;
}
return b;
}
int main()
{
int T;
f >> T;
precalcPower();
while(T--)
{
Solve();
Solve2();

int cnt = Partial[N][M];
res += cnt;
long long d = CMMDC(res, Power[cnt]);
g << res / d << "/" << Power[cnt] / d << "\n";
res = 0;
}

return 0;
}
``````