2861.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2861  User Id:fzk 
#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( "%d\n", ans/3 );
}
int main( ){
	input( );
	doit( );
	return 0;
}