Cod sursa(job #1230866)

Utilizator SmarandaMaria Pandele Smaranda Data 19 septembrie 2014 12:32:25
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 7.42 kb
#include <cstdio>
#include <cstring>

using namespace std;

int sp1 [55][55], sp2 [55][55], a [51][51], aria [10001], dp [55][55], aux [10001], ans [10001];
char s [55];
int n, m;
long long num = 0;

void read () {
    int i, j;
    scanf ("%d%d\n", &n, &m);
    for (i = 1; i <= n; i ++) {
        gets (s + 1);
        for (j = 1; j <= m; j ++) {
            a [i][j] = s [j] - '0';
            sp1 [i][j] = sp1 [i][j - 1] + a [i][j];
            sp2 [i][j] = sp2 [i - 1][j] + a [i][j];
            if (a [i][j] == 1)
                num ++;
        }
    }
}

void reset () {
    memset (sp1, 0, sizeof (sp1));
    memset (sp2, 0, sizeof (sp2));
    memset (dp, 0, sizeof (dp));
    num = 0;
    aria [0] = 1;
    aria [1] = 0;
}

void adunare (const int &value) {
    int i, tr;
    aria [1] += value;
    tr = aria [1] / 10;
    aria [1] = aria [1] % 10;
    i = 2;
    while (tr) {
        aria [i] += tr;
        tr = aria [i] / 10;
        aria [i] = aria [i] % 10;
        i ++;
    }
    -- i;
    if (i > aria [0])
        aria [0] = i;
}

void makeDp () {
    int i, j;
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++)
            dp [i][j] = dp [i - 1][j] + dp [i][j - 1] - dp [i - 1][j - 1] + a [i][j];
}

void impartire (int x [], long long value, int ans []) {
    long long d = 0, r = 0;
    int i = 1, st, dr, f;
    if (value == 0)
        return ;
    st = 1;
    dr = x [0];
    while (st < dr) {
        f = x [st];
        x [st] = x [dr];
        x [dr] = f;
        st ++; dr --;
    }
    while (d < value && i <= x [0]) {
        d = 1ll * d * 10 + x [i];
        i ++;
    }
    -- i;
    ans [0] = 0;
    for (; i <= x [0]; i ++) {
        ans [++ ans [0]] = d / value;
        r = d - 1ll * (1ll * d / value) * value;
        if (i + 1 <= x [0])
            d = 1ll * r * 10 + x [i + 1];
    }
}

long long impartire1 (int x [], long long value) {
    long long d = 0, r = 0;
    int i = 1, f, st ,dr;
    st = 1;
    dr = x [0];
    while (st < dr) {
        f = x [st];
        x [st] = x [dr];
        x [dr] = f;
        st ++; dr --;
    }
    while (d < value && i <= x [0]) {
        d = 1ll * d * 10 + x [i];
        i ++;
    }
    -- i;
    if (d < value)
        return d;
    for (; i <= x [0]; i ++) {
       r = d - 1ll * (1ll * d / value) * value;
        if (i + 1 <= x [0])
              d = 1ll * r * 10 + x [i + 1];
    }
    return r;
}

long long gcd () {
    long long d, c, r;
    memcpy (aux, aria, sizeof (aux));
    d = impartire1 (aux, num);
    c = num;
    while (d) {
        r = c % d;
        c = d;
        d = r;
    }
    return c;
}

void solve () {
    int i, j, k, l, l1, l2, l3, l4, h, ll1, ll2, ll3, ll4;
    long long g, cmmdc;
    adunare (num);
    num = (1ll << num);
    makeDp ();
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= m; j ++)
            for (k = i; k <= n; k ++)
                for (l = j; l <= m; l ++)
                    if (!(i == k && l == j)) {
                        l1 = sp1 [i][l] - sp1 [i][j - 1];
                        l2 = sp1 [k][l] - sp1 [k][j - 1];
                        l3 = sp2 [k][j] - sp2 [i - 1][j];
                        l4 = sp2 [k][l] - sp2 [i - 1][l];
                        g  = 1;
                        if (l1 && l2 && l3 && l4) {
                            h = (dp [k][l] - dp [i - 1][l] - dp [k][j - 1] + dp [i - 1][j - 1]);
                            if (i == k || j == l) {
                                h = h - 2;
                                g = (1ll << h);
                            }
                            else {
                                ll1 = l1 - a [i][j] - a [i][l];
                                if (ll1 != 0) {
                                    g = 1ll * g * ll1;
                                    h --;
                                }
                                ll2 = l2 - a [k][j] - a [k][l];
                                if (ll2 != 0) {
                                    g = 1ll * g * ll2;
                                    h --;
                                }
                                ll3 = l3 - a [i][j] - a [k][j];
                                if (ll3 != 0) {
                                    g = 1ll * ll3;
                                    h --;
                                }
                                ll4 = l4 - a [i][l] - a [k][l];
                                if (ll4 != 0) {
                                    g = 1ll * g * ll4;
                                    h --;
                                }
                                if (a [i][j]) {
                                    if (ll1 == 0)  {
                                        h --;
                                        ll1 = 1;
                                    }
                                    else
                                        if (ll3 == 0) {
                                            h --;
                                            ll3 = 1;
                                        }
                                }
                                if (a [i][l]) {
                                    if (ll1 == 0) {
                                        h --;
                                        ll1 = 1;
                                    }
                                    else
                                        if (ll4 == 0) {
                                            h --;
                                            ll4 = 1;
                                        }
                                }
                                if (a [k][j])  {
                                    if (ll3 == 0) {
                                        h --;
                                        ll3 = 1;
                                    }
                                    else
                                        if (ll2 == 0) {
                                            h --;
                                            ll2 = 1;
                                        }
                                }
                                if (a [k][l]) {
                                    if (ll2 == 0) {
                                        h --;
                                        ll2 = 1;
                                    }
                                    else
                                        if (ll4 == 0) {
                                            ll4 = 1;
                                            h --;
                                        }
                                }
                                g = 1ll * g * (1ll << h);
                            }
                            g = 1ll * g * (k - i + 1) * (l - j + 1);
                            adunare (g);
                            //aria = 1LL * aria + (k - i + 1) * (j - l + 1);
                        }
                    }
    cmmdc = gcd ();
    impartire (aria, cmmdc, ans);
    if (cmmdc)
        num = 1ll * num / cmmdc;
    for (i = 1; i <= ans [0]; i ++)
        printf ("%d", ans [i]);
    printf ("/%d\n", num);
}

int main () {
    int T, t;

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

    scanf ("%d", &T);
    for (t = 1; t <= T; t ++) {
        read ();
        solve ();
        reset ();
    }
    return 0;
}