# 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;
}

```
This entry was posted in poj. Bookmark the permalink.