Cod sursa(job #1230987)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 19 septembrie 2014 13:52:27
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.52 kb
#include <iostream>
#include <fstream>
using namespace std;

//#define lsb(X)(X&(X^(X-1)))



#define ll long long
#define cout g

ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
#define LE 66

ll lsb(ll v1,ll v2)
{
    while (v1&&v2)
    {
        if (v1>v2) v1%=v2;
        else v2%=v1;
    }

    if (v1) return v1;
    return v2;
}

ll sp[LE][LE],P[LE],B[6],MA[6],A[LE][LE];

ll nrz(ll i1,ll j1,ll i2,ll j2)
{
    if (i1>i2||j1>j2) return 0;
    return sp[i2][j2]-sp[i2][j1-1]-sp[i1-1][j2]+sp[i1-1][j1-1];
}

ll count(ll A[])
{
    int i,j;
    ll result=0;

    for(i=0; i<(1<<4); ++i)
    {
        int nrb=0;
        for(j=0; j<4; ++j)
        {
            B[j]=A[j];
            nrb+=((i&(1<<j))?1:0);
        }
        for(j=0; j<2; ++j) B[j]+=((i&(1<<j))?1:0);
        for(j=2; j<4; ++j) B[j]-=((i&(1<<j))?1:0);

        result+=P[  nrz(B[0],B[1],B[2],B[3])  ]*(ll)(nrb%2==0?(ll)1:(ll)-1) ;
    }

    return result;
}


pair<ll,ll> V[666];
#define x first
#define y second
#define mp make_pair


void brut(ll n,ll m,ll nrz)
{
   ll i,j,k=0,result=0;

   if (nrz==0)
  {
            cout<<"0/1"<<'\n';
          return;
        }

   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j)
       if (A[i][j])
        V[++k]=make_pair(i,j);

   for(i=1;i<(1<<k);++i)
   {
       ll Nmin=n,Nmax=1,Mmin=m,Mmax=1;

       for(j=0;j<k;++j)
         if (i&(1<<j))
         {
             Nmin=min(Nmin,V[j+1].x);
             Nmax=max(Nmax,V[j+1].x);
             Mmin=min(Mmin,V[j+1].y);
             Mmax=max(Mmax,V[j+1].y);
         }
         result+=(Nmax-Nmin+1)*(Mmax-Mmin+1);
   }

   ll lcm=lsb(result,P[k]);
   result/=lcm;
   cout<<result<<"/"<<P[k]/lcm;
}


int main()
{
    ll n,m,i,j,t,k,nrt;
    f>>nrt;

    for(i=1,P[0]=1; i<=55; ++i) P[i]=(P[i-1]*(ll)2);

    for(; nrt; --nrt)
    {
        f>>n>>m;
        f.get();
        ll suma=0,result=0;

        for(i=1; i<=n; ++i)
        {
            string str;
            f>>str;
            for(j=0; j<m; ++j) suma+=(A[i][j+1]=str[j]-'0');
        }

        for(i=1; i<=n; ++i)
            for(j=1; j<=m; ++j)
                sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+A[i][j];

        if (suma==0)
        {
            cout<<"0/1"<<'\n';
            continue;
        }

        for(i=1; i<=n; ++i)
            for(j=1; j<=m; ++j)
                for(t=i; t<=n; ++t)
                    for(k=j; k<=m; ++k)
                    {
                        if (i==t)
                        {
                            if (A[i][j]==0||A[t][k]==0) continue;
                            result+=P[nrz(i,j+1,t,k-1)]*(t-i+1)*(k-j+1);
                        }
                        else

                            if (j==k)
                            {
                                if (A[i][j]==0||A[t][k]==0) continue;
                                result+=P[nrz(i+1,j,t-1,k)]*(t-i+1)*(k-j+1);
                            }
                            else

                                if (i!=t&&j!=k)
                                {
                                    MA[0]=i,MA[1]=j,MA[2]=t,MA[3]=k;
                                    result+=count(MA)*(t-i+1)*(k-j+1);
                                }
                    }

        ll jos=P[suma];
        ll lcm=lsb(result,(P[suma]));
        jos/=lcm;
        result/=lcm;
        cout<<result<<"/"<<jos<<'\n';
       // brut(n,m,suma);
       // cout<<'\n'<<'\n';
    }

    return 0;
}