Cod sursa(job #1862465)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 29 ianuarie 2017 22:58:39
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <fstream>
using namespace std;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
int N, M;
long long Matrix[55][55];
long long Partial[55][55];
long long Power[55];
long long L[55][55], C[55][55];
int la[5], c[5];
long long res, ans;
int x[5];
bool Use[5];
long long p = 1;
void precalcPower()
{
    Power[0] = 1;
    for(int i = 1; i <= 50; i++)
        Power[i] = Power[i - 1] * 2;
}
void Read()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            char ch;
            f >> ch;
            Matrix[i][j] = ch - '0';
            Partial[i][j] = Partial[i - 1][j] + Partial[i][j - 1] - Partial[i - 1][j - 1] + Matrix[i][j];
            L[i][j] = L[i][j - 1] + Matrix[i][j];
            C[i][j] = C[i - 1][j] + Matrix[i][j];
        }
}

inline long long nb1(int i1, int j1, int i2, int j2)
{
    if(i1 > i2 || j1 > j2)
        return 0;
    return Partial[i2][j2] - Partial[i1 - 1][j2] - Partial[i2][j1 - 1] + Partial[i1 - 1][j1 - 1];
}
void back(int k)
{
    for(int i = x[k - 1] + 1; i <= 4; i++)
    {
        if(c[i] == 0)
            continue;
        x[k] = i;
        Use[i] = 1;
        long long aux = 1;
        for(int p = 1; p <= 4; p++)
        {
            int next = p + 1;
            if(next == 5)
                next = 1;
            if(Use[p] == 1 || Use[next] == 1)
                aux *= Power[la[p]];
            else
                aux *= (Power[la[p]] - 1);
        }
        ans += aux;
        if(k < 4)
            back(k + 1);
        Use[i] = 0;
    }
}
void Solve()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            for(int k = i + 1; k <= N; k++)
            {
                int ind = 0;
                for(int l = j + 1; l <= M; l++)
                {
                    Use[1] = Use[2] = Use[3] = Use[4] = 0;
                    la[1] = L[i][l - 1] - L[i][j];
                    la[2] = C[k - 1][l] - C[i][l];
                    la[3] = L[k][l - 1] - L[k][j];
                    la[4] = C[k - 1][j] - C[i][j];
                    p = (Power[la[1]] - 1) * (Power[la[2]] - 1) * (Power[la[3]] - 1) * (Power[la[4]] - 1);
                    c[1] = Matrix[i][j];
                    c[2] = Matrix[i][l];
                    c[3] = Matrix[k][l];
                    c[4] = Matrix[k][j];
                    ans = 0;
                    back(1);
                    ans += p;
                    res += 1LL * (l - j + 1) * (k - i + 1) * ans * (Power[nb1(i + 1, j + 1, k - 1, l - 1)]);
                }

            }
        }
}

void Solve2()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            if(Matrix[i][j] == 0)
            continue;
            for(int k = j + 1; k <= M; k++)
            {
                if(Matrix[i][k] == 0)
                    continue;
                res += Power[(L[i][k - 1] - L[i][j])] * (k - j + 1);
            }
        }
    for(int i = 1; i <= M; i++)
        for(int j = 1; j <= N; j++)
        {
            if(Matrix[j][i] == 0)
                continue;
            for(int k = j + 1; k <= N; k++)
            {
                if(Matrix[k][i] == 0)
                    continue;
                res += Power[(C[k - 1][i] - C[j][i])] * (k - j + 1);
            }

        }
}
long long CMMDC(long long a, long long b)
{
    long long r = a % b;
    while(r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
int main()
{
    int T;
    f >> T;
    precalcPower();
    while(T--)
    {
        Read();
        Solve();
        Solve2();

        int cnt = Partial[N][M];
        res += cnt;
        long long d = CMMDC(res, Power[cnt]);
        g << res / d << "/" << Power[cnt] / d << "\n";
        res = 0;
    }


    return 0;
}