Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #3348232) | Diferente pentru utilizator/raresh intre reviziile 7 si 21 | Diferente pentru utilizator/raresh intre reviziile 4 si 21 | Cod sursa (job #3332157)
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
using dbl=long double;
constexpr int NMAX=64;
constexpr ll MOD=1'000'000'000;
int N, M;
char s[NMAX];
int mat[NMAX][NMAX];
ll countWays(int i0, int i1)
{
int i, j, k, l;
ll dp[2][2][NMAX][NMAX];
memset(dp, 0, sizeof(dp));
for(j=0;j<M;++j)
{
for(i=i0;i<=i1;++i)
{
if(mat[i][j])
{
for(k=0;k<=j;++k)
for(l=j;l>=k;--l)
{
dp[1][1][k][j]+=dp[1][1][k][l];
dp[i==i0][1][k][j]+=dp[0][1][k][l];
dp[1][i==i1][k][j]+=dp[1][0][k][l];
dp[i==i0][i==i1][k][j]+=dp[0][0][k][l];
}
++dp[i==i0][i==i1][j][j];
}
}
}
auto d=dp[1][1];
ll ans=0;
for(i=0;i<M;++i)
for(j=i;j<M;++j)
ans+=d[i][j]*(j-i+1LL);
return ans;
}
std::pair<ll, ll> solve()
{
int i, j, flag;
do
{
flag=0;
for(i=0;i<N;++i)
flag+=mat[i][M-1];
if(!flag)
--M;
}while(!flag && M);
if(!M)
return {0LL, 1LL};
do
{
flag=0;
for(i=0;i<M;++i)
flag+=mat[N-1][i];
if(!flag)
--N;
}while(!flag);
do
{
flag=0;
for(i=0;i<N;++i)
flag+=mat[i][0];
if(!flag)
{
--M;
for(i=0;i<N;++i)
for(j=0;j<M;++j)
mat[i][j]=mat[i][j+1];
}
}while(!flag);
do
{
flag=0;
for(i=0;i<N;++i)
flag+=mat[0][i];
if(!flag)
{
--N;
for(i=0;i<N;++i)
for(j=0;j<M;++j)
mat[i][j]=mat[i+1][j];
}
}while(!flag);
if(M<N)
{
for(i=0;i<N;++i)
for(j=i+1;j<M;++j)
std::swap(mat[i][j], mat[j][i]);
std::swap(N, M);
}
int i0, i1;
ll top=0, bot=1;
for(i=0;i<N;++i)
for(j=0;j<M;++j)
bot<<=mat[i][j];
for(i0=0;i0<N;++i0)
for(i1=i0;i1<N;++i1)
top+=(i1-i0+1)*countWays(i0, i1);
ll d=std::gcd(top, bot);
top/=d;
bot/=d;
return {top, bot};
}
int main()
{
FILE* f=fopen("boundingbox.in", "r"), *g=fopen("boundingbox.out", "w");
int _, i, j;
fscanf(f, "%d", &_);
do
{
fscanf(f, "%d%d", &N, &M);
fgets(s, NMAX, f);
for(i=0;i<N;++i)
{
fgets(s, NMAX, f);
for(j=0;j<M;++j)
mat[i][j]=s[j]-'0';
}
auto p=solve();
fprintf(g, "%lld/%lld\n", p.first, p.second);
}while(--_);
fclose(f);
fclose(g);
return 0;
}