posts - 195,  comments - 30,  trackbacks - 0
#include <cstdio>
#include 
<string>

int b[51][51][50], N;

void add ( int i, int j )
{
    
int k;
    
for ( k = 0; k < 50; k ++ )
        b[i][j][k] 
= b[i - 1][j - 1][k] + b[i - 1][j][k] * j;
    
int c = 0, t;
    
for ( k = 0; k < 50; k ++ )
    
{
        t 
= b[i][j][k] + c;
        c 
= t / 10;
        b[i][j][k] 
= t % 10;
    }

}


void dp ()
{
    memset ( b, 
0x00sizeof ( b ) );
    
int i, j;
    
for ( i = 1; i <= 50; i ++ )
    
{
        b[i][
1][0= b[i][i][0= 1;
    }

    
for ( i = 3; i <= 50; i ++ )
    
{
        
for ( j = 2; j < i; j ++ )
        
{
            add ( i, j );
        }

    }

}


void print ( int i, int j )
{
    
int k;
    
for ( k = 49; k >= 0; k -- )
        
if ( b[i][j][k] )
            
break;
    
if ( k == -1 )
        printf ( 
"0" );
    
for ( ; k >= 0; k -- )
        printf ( 
"%d", b[i][j][k] );
    printf ( 
" " );
}


void print ( int n )
{
    printf ( 
"%d ", n );
    
int i, j, k;
    
int ans[50];
    memset ( ans, 
0sizeof ( ans ) );
    
for ( i = 1; i <= n; i ++ )
    
{
        
for ( j = 0; j < 50; j ++ )
        
{
            ans[j] 
+= b[n][i][j];
        }

    }

    
int t, c = 0;
    
for ( k = 0; k < 50; k ++ )
    
{
        t 
= ans[k] + c;
        c 
= t / 10;
        ans[k] 
= t % 10;
    }

    
for ( k = 49; k >= 0; k -- )
        
if ( ans[k] )
            
break;
    
if ( k == -1 )
        printf ( 
"0" );
    
for ( ; k >= 0; k -- )
        printf ( 
"%d", ans[k] );
    printf ( 
" " );
}


int main ()
{
    
//freopen ( "in.txt", "r", stdin );
    dp ();
    
//print ( 5, 2 );
    while ( scanf ( "%d"&N ) && N )
    
{
        print ( N );
    }

    
return 0;
}

Rhyme Schemes
Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
stdin/stdout 3s 8192K 97 55 Special Test

The rhyme scheme for a poem (or stanza of a longer poem) tells which lines of the poem rhyme with which other lines. For example, a limerick such as


If computers that you build are quantum
Then spies of all factions will want 'em
Our codes will all fail
And they'll read our email
`Til we've crypto that's quantum and daunt 'em
Jennifer and Peter Short(http://www.research.att.com/~shor/notapoet.html)
Has a rhyme scheme of aabba, indicating that the first, second and fifth lines rhyme and the third and fourth lines rhyme.

For a poem or stanza of four lines, there are 15 possible rhyme schemes: aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, and abcd.

Write a program to compute the number of rhyme schemes for a poem or stanza of N lines where N is an input value.

Input

Input will consist of a sequence of integers N, one per line, ending with a 0 (zero) to indicate the end of the data. N is the number of lines in a poem.

Output

For each input integer N, your program should output the value of N, followed by a space, followed by the number of rhyme schemes for a poem with N lines as a decimal integer with at least 12 correct significant digits (use double precision floating point for your computations).

Sample Input

1
2
3
4
20
30
10
0

Sample Output

1 1
2 2
3 5
4 15
20 51724158235372
30 846749014511809120000000
10 115975


 
排列组合的题目,大致上从小到大顺推即可。设b[i][j]中i表示字符串长度,j表示字符串中用到的字母个数,不难推出b[i][j] = b[i-1][j-1] + b[i - 1][j] * j。
而我自己的思路一直是想根据最后的那一个字母来推,推不出来

posted on 2009-05-12 11:42 luis 阅读(337) 评论(0)  编辑 收藏 引用 所属分类: 组合数学

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年3月>
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜