Poj Solution 2861

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

#include <stdio.h>
#include <memory.h>

bool e[120][120];
int s[120][120];
int n;
void input( ) {
    int i, j, k;
    char c[2];
    scanf( "%d", &n );
    for( i=0; i<n; i++ ) {
        for( j=0; j<n; j++ ) {
            scanf( "%1s", c );
            e[i][j] = ( i!=j && c[0] == '1' );
        }
    }
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ ) {
        s[i][j] = 0;
        for( k=0; k<n; k++ )
            if( e[i][k] && e[j][k] )
                s[i][j]++;
        s[j][i] = s[i][j];
    }
}
void doit( ) {
    int i, j, k;
    int ans = 0, sum, t, tt;    
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ ) {
        sum = 0;
        for( k=0; k<n; k++ ) {
            if( e[i][k] && k!=j ) {
                t = s[k][j];
                if( e[i][j] ) t--;
                ans += sum * t % (9901*3);
                sum += t;
            }
        }        
        for( k=0; k<n; k++ )
            if( e[k][j] && k!=i ) {
                t = s[k][i];
                if( e[i][j] ) t--;
                ans -= t*(t-1)/2;
            }
        for( k=0; k<n; k++ )
            if( e[i][k] && e[j][k] ) {
                t = s[k][i];
                tt = s[k][j];
                if( e[i][j] )
                    t--, tt--;
                ans -= t*tt;
            }
        ans %= (9901*3);
    }
    for( i=0; i<n; i++ )
    for( j=i+1; j<n; j++ )
        if( e[i][j] ) {
            ans += s[i][j]*(s[i][j]-1)/2;
        }
    ans %=  (9901*3);
    if( ans < 0 ) ans += (9901*3);
    printf( "%dn", ans/3 );
}
int main( ){
    input( );
    doit( );
    return 0;
}

    
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *