# Poj Solution 2861

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

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

bool e;
int s;
int n;
void input( ) {
int i, j, k;
char c;
scanf( "%d", &n );
for( i=0; i<n; i++ ) {
for( j=0; j<n; j++ ) {
scanf( "%1s", c );
e[i][j] = ( i!=j && c == '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.