1187.txt

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

#include <stdio.h>

int s[31][11][11][11];

int get( int d, int l1, int l2, int l3 )
{
    int t, j, k, i, h;
    
    if( l1 == 0 && l2 == 0 && l3 == 0 && d >= 0 )
    	return 1;
	
 	if( d <= 0 )
    	return 0;
    	
	if( ( t = s[d][l1][l2][l3] ) >= 0 )
		return t;
		
	t = 0;
	
	if( d == 1 )
	{
	    if( l1 ) t += get( d, l1-1, l2, l3 );
	    if( l2 ) t += get( d, l1, l2-1, l3 );
	    if( l3 ) t += get( d, l1, l2, l3-1 );
     	
     	t %= 11380;
      	s[d][l1][l2][l3] =  t;
	    return t ;
	}    
	
 	for( i=0; i<=l1-1; i++ )
	for( j=0; j<=l2; j++ )
 	for( k=0; k<=l3; k++ )
  	{
       	t += ( get( d-1, i, j, k ) * get( d, l1-1-i, l2-j, l3-k ) );
        if( t > ( 1 << 30 ) ) t %= 11380;
    }    
  	
	for( j=0; j<=l2-1; j++ )
	for( k=0; k<=l3; k++ )
	{
     	t += ( get( d-1, 0, j, k ) * get( d, l1, l2-1-j, l3-k ) );
 	 	if( t > ( 1 << 30 ) ) t %= 11380;
   	}  	 
	
	for( k=0; k<=l3-1; k++ )
	{
     	t += ( get( d-1, 0, 0, k ) * get( d, l1, l2, l3-1-k ) );
 	 	if( t > ( 1 << 30 ) ) t %= 11380;
   	}  	 

	t %= 11380;
	s[d][l1][l2][l3] = t;
	
	return t;
}

int main()
{
    int d, l1, l2, l3, i, j, k, l;
    
 	scanf( "%d %d %d %d", &l1, &l2, &l3, &d );
 	
 	for( l=0; l<=d; l++ )
 	for( i=0; i<=l1; i++ )
 	for( j=0; j<=l2; j++ )
 	for( k=0; k<=l3; k++ )
 		s[l][i][j][k] = -1;
 		
	printf( "%d\n", ( get( d, l1, l2, l3 ) - get( d-1, l1, l2, l3 ) + 11380 ) % 11380 );
	
	return 0;
}