Cod sursa(job #1467720)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 4 august 2015 00:08:40
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.59 kb
#include<bits/stdc++.h>

using namespace std;

#define dbg(x) (cout<<#x<<" = "<<(x)<<'\n')

typedef long long int lld;
const int INF = (1LL << 30) - 1;
const lld LINF = (1LL << 62) - 1;

void clear(), read(), precompute(), solve(), print();

int T, N, M;
char A[55][55];
int B[55][55];
lld totalArea, totalNumber;

int main() {
    freopen("boundingbox.in", "r", stdin);
    freopen("boundingbox.out", "w", stdout);

    scanf("%d", &T);

    while (T--) {
        clear();
        read();
        precompute();
        solve();
        print();
    }

    return 0;
}

void clear() {
    totalArea = 0;
    totalNumber = 0;
}

void read() {
    scanf("%d%d", &N, &M);

    for (int i = 1; i <= N; i++)
        scanf("%s", A[i] + 1);
}

void precompute() {
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            B[i][j] = B[i - 1][j]  + B[i][j - 1] - B[i - 1][j - 1] + A[i][j] - '0';

    totalNumber = (1LL << B[N][M]);
}

int query(int i, int j, int k, int l) {
    if (i > k || j > l)
        return 0;

    return B[i - 1][j - 1] + B[k][l] - B[i - 1][l] - B[k][j - 1];
}

void solve() {
    int i, j, k, l;
    int n, e, s, w, c;
    int area;
    lld nr;
    lld number;
    bool L[4];
    lld mlc = 0;

    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            for (k = i + 1; k <= N; k++)
                for (l = j + 1; l <= M; l++) {
                    /* setup */

                    area = (k - i + 1) * (l - j + 1);
                    number = 0;

                    n = query(i, j + 1, i, l - 1);
                    e = query(i + 1, l, k - 1, l);
                    s = query(k, j + 1, k, l - 1);
                    w = query(i + 1, j, k - 1, j);
                    c = query(i + 1, j + 1, k - 1, l - 1);

                    /* compute */

                    for (int mask = 0; mask < 16; mask++) {
                        L[0] = ((mask >> 0) & 1) | ((mask >> 1) & 1);
                        L[1] = ((mask >> 1) & 1) | ((mask >> 2) & 1);
                        L[2] = ((mask >> 2) & 1) | ((mask >> 3) & 1);
                        L[3] = ((mask >> 3) & 1) | ((mask >> 0) & 1);

                        nr = 1;
                        nr *= ((1LL << n) - (!L[0]));
                        nr *= ((1LL << e) - (!L[1]));
                        nr *= ((1LL << s) - (!L[2]));
                        nr *= ((1LL << w) - (!L[3]));

                        if ((mask >> 0) & 1)
                            nr *= (A[i][j] - '0');
                        if ((mask >> 1) & 1)
                            nr *= (A[i][l] - '0');
                        if ((mask >> 2) & 1)
                            nr *= (A[k][l] - '0');
                        if ((mask >> 3) & 1)
                            nr *= (A[k][j] - '0');

                        number += nr;
                    }

                    number *= (1LL << c);

                    /* add to solution */

                    totalArea += area * number;
                    mlc += number;
                }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++) {
            for (k = i + 1; k <= N; k++) {
                /* setup */

                area = (k - i + 1);
                number = 0;

                n = query(i, j, i, j);
                s = query(k, j, k, j);
                c = query(i + 1, j, k - 1, j);

                /* compute */

                number += n * s * (1LL << c);

                /* add to solution */

                totalArea += area * number;
                mlc += number;
            }

            for (l = j + 1; l <= M; l++) {
                /* setup */

                area = (l - j + 1);
                number = 0;

                /* compute */

                w = query(i, j, i, j);
                e = query(i, l, i, l);
                c = query(i, j + 1, i, l - 1);

                number += w * e * (1LL << c);

                /* add to solution */

                totalArea += area * number;
                mlc += number;
            }

            /* setup */

            area = 1;
            number = 0;

            /* compute */

            number += (A[i][j] - '0');

            /* add to solution */

            totalArea += area * number;
            mlc += number;
        }

//    dbg(mlc + 1);
//    dbg(totalNumber);
}

void print() {
    lld d = totalArea ? __gcd(totalArea, totalNumber) : totalNumber;

    totalArea /= d;
    totalNumber /= d;

    printf("%lld/%lld\n", totalArea, totalNumber);
}