Cod sursa(job #1230868)

Utilizator atatomirTatomir Alex atatomir Data 19 septembrie 2014 12:35:12
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.66 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define maxComb 50

long t,i,j,i2,j2,ti;
long long a,b,c[maxComb+10][maxComb+10];
long n,m,sum[maxComb+10][maxComb+10];
char s[maxComb+10];

long long ansA,ansB,cmm;
long cont;
long long temp;

long long p1 ;
long long p2 ;
long long p3 ;
long long p4 ;
long long e[5];

void preCalculate() {
    c[0][0] = 1;
    for(long i=1;i<=maxComb;i++){
        c[i][0] = 1;
        for(long j=1;j<=i;j++) c[i][j] = c[i-1][j-1] + c[i-1][j];
    }

}

inline long exist(long i,long j,long i2,long j2){
    if(i > i2 || j > j2) return 0;
    return (sum[i2][j2] - sum[i-1][j2] - sum[i2][j-1] + sum[i-1][j-1]);
}

bool valid(long i,long j,long i2,long j2){
    if(exist(i,j,i,j2))
        if(exist(i2,j,i2,j2))
            if(exist(i,j,i2,j))
                if(exist(i,j2,i2,j2))
                    return true;
    return false;
}

long long cmmdc(long long a,long long b){
    long long t;
    if(a < b) {t=a;a=b;b=t;}
    while(b){
        a = a%b;
        t=a;a=b;b=t;
    }
    return a;
}

void Recurs(long pas,long ind1,long ind2,long ind3,long ind4){
    if(pas > 4){
        long long ans=1,v;
        long long v1 = 1LL << p1;
        long long v2 = 1LL << p2;
        long long v3 = 1LL << p3;
        long long v4 = 1LL << p4;

        temp = temp + (v1-ind1) * (v2 - ind2) * (v3 - ind3) * (v4 - ind4);
        return;
    }

    Recurs(pas+1,ind1,ind2,ind3,ind4);
    if(e[pas]){
        switch(pas){
            case 1: ind1=ind4=0;
                    break;
            case 2: ind1=ind2=0;
                    break;
            case 3: ind3=ind4=0;
                    break;
            case 4: ind2=ind3=0;
                    break;
        }
        Recurs(pas+1,ind1,ind2,ind3,ind4);
    }
}

long long edge(long i,long j,long i2,long j2){
    p1 = exist(i,j+1,i,j2-1);
    p2 = exist(i+1,j2,i2-1,j2);
    p3 = exist(i2,j+1,i2,j2-1);
    p4 = exist(i+1,j,i2-1,j);

    e[1] = exist(i,j,i,j);
    e[2] = exist(i,j2,i,j2);
    e[3] = exist(i2,j,i2,j);
    e[4] = exist(i2,j2,i2,j2);

    long long inside = exist(i+1,j+1,i2-1,j2-1);
    inside = 1LL << inside;

    if(i == i2 && j == j2) return 1;
    if(i == i2) {
        inside = 1LL << exist(i,j+1,i,j2-1);
        return inside;
    }
    if(j == j2) {
        inside = 1LL << exist (i+1,j,i2-1,j);
        return inside;
    }

    temp = 0;
    Recurs(1,1,1,1,1);
    return temp*inside;
}

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

    preCalculate();

    scanf("%ld",&t);
    for(ti=1;ti<=t;ti++){
        memset(sum,0,sizeof(sum));
        cont = 0;

        scanf("%ld %ld\n",&n,&m);
        for(i=1;i<=n;i++){
            scanf("%s\n",s);
            for(j=1;j<=m;j++){
                if(s[j-1] == '1') sum[i][j] = 1,cont++;
                sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }

        ansA = 0; ansB = (cont != n*m?1:0);

        for(i=1;i<=cont;i++) ansB = ansB + c[cont][i];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(i2=i;i2<=n;i2++)
                    for(j2=j;j2<=m;j2++)
                        if(valid(i,j,i2,j2)){
                            ansA = ansA + 1LL*((i2-i+1)*(j2-j+1))*edge(i,j,i2,j2);
                            //printf("%lld!!\n",1LL*((i2-i+1)*(j2-j+1))*edge(i,j,i2,j2));
                        }


        cmm = cmmdc(ansA,ansB);
        ansA = ansA / cmm;
        ansB = ansB / cmm;

        printf("%lld/",ansA);
        printf("%lld\n",ansB);
    }

    return 0;
}