Cod sursa(job #3332166)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 4 ianuarie 2026 18:13:44
Problema Boundingbox Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
// 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];
			}
		}
	}

	ll ans=0;
	for(i=0;i<M;++i)
		for(j=i;j<M;++j)
			ans+=dp[1][1][i][j]*(j-i+1LL);

	return ans;
}

std::pair<ll, ll> solve()
{
	int i, j;

	if(M<N)
	{
		for(i=0;i<NMAX;++i)
			for(j=0;j<NMAX;++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+1LL)*countWays(i0, i1);

	ll d=std::gcd(top, bot);
	top/=d;
	bot/=d;
	return {top, bot};
}

std::pair<ll, ll> brut()
{
	std::vector<int> x, y;
	int i, j;
	ll top=0, bot=1;

	for(i=0;i<N;++i)
		for(j=0;j<M;++j)
			if(mat[i][j])
			{
				bot<<=1;
				x.push_back(i);
				y.push_back(j);
			}

	for(int mask=(1<<sz(x))-1;mask>0;--mask)
	{
		int xm=N, xM=0, ym=M, yM=0;
		for(i=0;i<sz(x);++i)
			if(mask&(1<<i))
			{
				xm=std::min(xm, x[i]);
				xM=std::max(xM, x[i]);
				ym=std::min(ym, y[i]);
				yM=std::max(yM, y[i]);
			}
		top+=(xM-xm+1LL)*(yM-ym+1LL);
	}

	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();
		// auto q=brut();
		// assert(p==q);
		fprintf(g, "%lld/%lld\n", p.first, p.second);
	}while(--_);

	fclose(f);
	fclose(g);
	return 0;
}