Pagini recente » Cod sursa (job #2102353) | Cod sursa (job #1334832) | Cod sursa (job #1858115) | Cod sursa (job #3151374) | Cod sursa (job #1230921)
#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 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]) ]*(nrb%2==0?1:-1) ;
}
return result;
}
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);
jos/=lcm;
result/=lcm;
cout<<result<<"/"<<jos<<'\n';
}
return 0;
}