Pagini recente » Cod sursa (job #618045) | Cod sursa (job #133129) | Cod sursa (job #2316300) | Cod sursa (job #1956420) | Cod sursa (job #1230792)
#include<fstream>
#define FOR(a,b,c) for(register int a=b;a<=c;++a)
#define ROF(a,b,c) for(register int a=b;a>=c;--a)
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<vector>
#define fi first
#define se second
#define FIT(a,b) for(vector<int>::iterator a=b.begin();a!=b.end();++a)
#include<ctime>
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<deque>
#define mod 1000000007
#define N 5000
#define SQ 1400
#define pb push_back
using namespace std;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
long long gcd(long long a,long long b)
{
if(!b)
return a;
return gcd(b,a%b);
}
long long freq[N],S,col[N][N],sum[N][N],lin[N][N],tot,kkt;
int n,m,T,i,j,k,l;
char s[N][N];
int main ()
{
f>>T;
while(T--)
{
f>>n>>m;
for(i=1;i<=n;++i)
f>>(s[i]+1);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
col[i][j]=lin[i][j]=sum[i][j]=0;
for(i=1;i<=n*m;++i)
freq[i]=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
{
col[i][j]=col[i-1][j]+(s[i][j]=='1');
lin[i][j]=lin[i][j-1]+(s[i][j]=='1');
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(s[i][j]=='1');
}
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
for(k=1;k<=m;++k)
for(l=k;l<=m;++l)
{
if((col[j][k]-col[i-1][k])&&(col[j][l]-col[i-1][l])&&(lin[j][l]-lin[j][k-1])&&(lin[i][l]-lin[i][k-1]))
{
if(i==j&&k==l)
{
freq[1]++;
continue;
}
if(i==j)
{
freq[l-k+1]+=(1LL<<(lin[j][l-1]-lin[j][k]));
continue;
}
if(k==l)
{
freq[j-i+1]+=(1LL<<(col[j-1][k]-col[i][k]));
continue;
}
int a11,a12,a21,a22;
a11=a12=a21=a22=0;
if(s[i][k]=='1')
a11=1;
if(s[i][l]=='1')
a12=1;
if(s[j][k]=='1')
a21=1;
if(s[j][l]=='1')
a22=1;
int plm=sum[j-1][l-1]-sum[i][l-1]-sum[j-1][k]+sum[i][k];
int l_j=lin[j][l-1]-lin[j][k];
int l_s=lin[i][l-1]-lin[i][k];
int c_d=col[j-1][l]-col[i][l];
int c_s=col[j-1][k]-col[i][k];
long long lj=(1LL<<l_j);
long long ls=(1LL<<l_s);
long long cs=(1LL<<c_s);
long long cd=(1LL<<c_d);
long long cur=0;
int area=(j-i+1)*(l-k+1);
cur+=(lj-1)*(ls-1)*(cs-1)*(cd-1);
if(a11)
cur+=ls*cs*(lj-1)*(cd-1);
if(a12)
cur+=ls*cd*(lj-1)*(cs-1);
if(a21)
cur+=lj*cs*(ls-1)*(cd-1);
if(a22)
cur+=lj*cd*(cs-1)*(ls-1);
if(a11&&a12)
cur+=ls*cs*cd*(lj-1);
if(a11&&a21)
cur+=cs*lj*ls*(cd-1);
if(a11&&a22)
cur+=cs*cd*lj*ls;
if(a12&&a21)
cur+=cs*cd*lj*ls;
if(a12&&a22)
cur+=lj*ls*cd*(cs-1);
if(a21&&a22)
cur+=lj*cs*cd*(ls-1);
if(a12&&a21&&a22)
cur+=cs*cd*lj*ls;
if(a11&&a21&&a22)
cur+=cs*cd*lj*ls;
if(a11&&a12&&a22)
cur+=cs*cd*lj*ls;
if(a11&&a12&&a21)
cur+=cs*cd*lj*ls;
if(a11&&a12&&a21&&a22)
cur+=cs*cd*lj*ls;
freq[area]+=cur*(1LL<<plm);
}
}
tot=1;
S=0;
for(i=1;i<=n*m;++i)
{
tot+=freq[i];
S+=freq[i]*i;
}
kkt=gcd(S,tot);
g<<S/kkt<<"/"<<tot/kkt<<"\n";
}
return 0;
}
//Look at me! Look at me! The monster inside me has grown this big!