Cod sursa(job #3302933)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 12 iulie 2025 10:35:18
Problema Boundingbox Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.26 kb
#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;
}