Poj Solution 3139

http://poj.org/problem?id=3139

#include <stdio.h>
#include <algorithm>
using namespace std;

int has_one[1<<16];

int ans[1<<16];
int result[1<<16][24];

int a[16];

void clac_has_one( ) {
    int i;
    has_one[0] = 0;
    for( i=1; i<(1<<16); i++ )
        has_one[i] = has_one[ i&(i-1) ] + 1;
}

void clac_result( ) {
    int i, j, k;
    int index[4];

    for( i=0; i<(1<<16); i++ ) {
        if( has_one[i] == 4 ) {
            k = 0;
            for( j=0; j<16; j++ )
                if( i & (1<<j) )
                    index[k++] = j;
            j = 0;
            do{
                result[i][j] = a[index[0]]*4 + a[index[1]]*3 
                    + a[index[2]]*2 + a[index[3]];
                j++;
            }while( next_permutation( index, index+4 ) );

            sort( result[i], result[i]+j );
        }
    }
}

int c_8_4[100][4];
int m;

void clac_c84( ) {
    int i, j, k;
    m = 0;
    for( i=0; i<(1<<7); i++ ) {
        if( has_one[i] == 4 ) {
            k = 0;
            for( j=0; j<7; j++ )
                if( i & (1<<j) )
                    c_8_4[m][k++] = j;
            m++;
        }
    }
}



void clac_ans( ) {
    int i, j, k, a, b, *ra, *rb, *ka, *kb, t;
    char counter[11000] = { 0 };

    int id[8];

    for( i=0; i<(1<<16); i++ ) {
        if( has_one[i] == 8 && ( i<(1<<15) || ans[((1<<16)-1)^i] ) ) {

            k = 0;
            for( j=0; j<16; j++ )
                if( i & (1<<j) )
                    id[k++] = j;
            t = 0;

            for( j=0; j<35; j++ ) {
                a = (1<<id[c_8_4[j][0]]) | (1<<id[c_8_4[j][1]]) 
                    | (1<<id[c_8_4[j][2]]) | (1<<id[c_8_4[j][3]]);
                b = i ^ a;
                ra = result[a];
                rb = result[b];
                ka = result[a] + 23;
                kb = result[b] + 23;
                if( *ra > *kb || *rb > *ka )
                    continue;

                while( ra<=ka )
                    counter[ *ra++ ]++;
                while( rb<=kb )
                    t += counter[ *rb++ ];
                ra = result[a];
                while( ra<=ka )
                    counter[ *ra++ ] = 0;
            }
            
            ans[i] = t;
        }
        else
            ans[i] = 0;
    }
    return ;
}

long long clac( ) {
    long long sum = 0;
    int i;

    for( i=0; i<(1<<15); i++ ) {
        if( has_one[i] == 8 ) {
            sum += (long long)ans[i]*ans[((1<<16)-1)^i];
        }
    }
    return sum;
}

int main( ) {
    int i, count=1;
    clac_has_one( );
    clac_c84( );

    while( true ) {
        scanf( "%d", &a[0] );
        if( a[0] == 0 ) break;

        for( i=1; i<16; i++ )
            scanf( "%d", &a[i] );

        clac_result( );

        clac_ans( );

        printf( "Case %d: %lldn", count++, clac() );
    }
    return 0;
}