Pagini recente » Cod sursa (job #3311765) | Cod sursa (job #3345728) | Cod sursa (job #3345722) | Cod sursa (job #3334771) | Cod sursa (job #3302933)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using ll = long long;
// voiam sa scriu MOD, gandindu-ma la 666013.
// stiai ca 1000000000000066600000000000001 e de asemenea prim? are 13 zerouri pe fiecare parte.
// very very evil number.
// osa mor de la atatea cazuri
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
ll cmmdc(ll a, ll b){
ll c = 0;
while(b){
c = a % b;
a = b;
b = c;
}
return a;
}
ll sp[55][55];
ll v[55][55];
ll cnt1(ll x, ll y, ll xx, ll yy){ // pe submat
// if(x > xx || y > yy) return 0;
return sp[xx][yy] - sp[x - 1][yy] - sp[xx][y - 1] + sp[x - 1][y - 1];
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
// lowkey inoptim codul da mai optimizez dupa ce am puncte :)
ll t; in >> t;
for(ll _i = 0; _i < t; _i++){
ll n, m; in >> n >> m;
for(ll i = 0; i <= n; i++){
for(ll j = 0; j <= m; j++) v[i][j] = sp[i][j] = 0;
}
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
char c; in >> c;
v[i][j] = c - '0';
sp[i][j] = sp[i][j - 1] + sp[i - 1][j] - sp[i - 1][j - 1] + v[i][j];
}
}
ll sum = 0;
ll total = 1; // cazul vid
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
for(ll ii = i; ii <= n; ii++){
for(ll jj = j; jj <= m; jj++){
ll cnt = 0;
if(i == ii && j == jj){
cnt = v[i][j]; // e doar 1 el
}else if(i == ii || j == jj){
if(v[i][j] != 1 || v[ii][jj] != 1) cnt = 0;
else if(i == ii) cnt = (1LL << cnt1(i, j + 1, ii, jj - 1));
else cnt = (1LL << cnt1(i + 1, j, ii - 1, jj));
}else{
ll c1 = v[i][j];
ll c2 = v[ii][j];
ll c3 = v[ii][jj];
ll c4 = v[i][jj]; // colturile pt cazuri speciale
ll v1 = cnt1(i + 1, j, ii - 1, j); // intre colturile 1 si 2
ll v2 = cnt1(ii, j + 1, ii, jj - 1); // intre colturile 2 si 3
ll v3 = cnt1(i + 1, jj, ii - 1, jj); // intre colturile 3 si 4
ll v4 = cnt1(i, j + 1, i, jj - 1); // ntre colturile 4 si 1
ll intr = cnt1(i + 1, j + 1, ii - 1, jj - 1); // tot interiorul
// phew, acuma vin cazuile alea ga- naspa
// general, aleg unul de pe fiecare latura distinct
cnt = (1LL << intr) * ((1LL << v1) - 1) * ((1LL << v2) - 1) * ((1LL << v3) - 1) * ((1LL << v4) - 1);
// aleg 1 colt singur (pe 2 lat) si celelalte dist
if(c1) cnt += ((1LL << v3) - 1) * ((1LL << v2) - 1) * (1LL << (v1 + v4 + intr));
if(c2) cnt += ((1LL << v3) - 1) * ((1LL << v4) - 1) * (1LL << (v1 + v2 + intr));
if(c3) cnt += ((1LL << v1) - 1) * ((1LL << v4) - 1) * (1LL << (v2 + v3 + intr));
if(c4) cnt += ((1LL << v1) - 1) * ((1LL << v2) - 1) * (1LL << (v3 + v4 + intr));
// aleg 2 colturi singure si celelalte dist
if(c1 && c2) cnt += ((1LL << v3) - 1) * (1LL << (v4 + v2 + v1 + intr));
if(c2 && c3) cnt += ((1LL << v4) - 1) * (1LL << (v1 + v3 + v2 + intr));
if(c3 && c4) cnt += ((1LL << v1) - 1) * (1LL << (v2 + v3 + v4 + intr));
if(c4 && c1) cnt += ((1LL << v2) - 1) * (1LL << (v1 + v3 + v4 + intr));
if(c1 && c3) cnt += (1LL << (intr + v1 + v2 + v3 + v4)); // tot e rezolvat
if(c2 && c4) cnt += (1LL << (intr + v1 + v2 + v3 + v4)); // tot e rezolvat
// aleg 3 colturi singure
if(c1 && c2 && c3) cnt += (1LL << (intr + v1 + v2 + v3 + v4));
if(c1 && c2 && c4) cnt += (1LL << (intr + v1 + v2 + v3 + v4));
if(c1 && c3 && c4) cnt += (1LL << (intr + v1 + v2 + v3 + v4));
if(c2 && c3 && c4) cnt += (1LL << (intr + v1 + v2 + v3 + v4));
// siii in final toate 4 (e acelasi caz copy paste)
if(c1 && c2 && c3 && c4) cnt += (1LL << (intr + v1 + v2 + v3 + v4));
}
// cout << "( " << i << " , " << j << " ) si ( " << ii << " , " << jj << " ) are " << cnt << " cazuri favorabile." << '\n';
sum += cnt * (ii - i + 1) * (jj - j + 1);
total += cnt;
}
}
}
}
ll d = cmmdc(sum, total);
sum /= d;
total /= d;
out << sum << "/" << total << '\n';
}
return 0;
}