记录编号	49505	评测结果	AAAAAAAAAA
题目名称	K 上升段	最终得分	100
用户昵称	小白	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-11-08 12:09:06	内存使用	1.80 MiB

/*
	求 n元集合的全排列的 k递增段排列的个数 
	dp方程：f( n, m ) = (n-m+1)*f( n-1, m-1 ) + m*f( n-1, m ) 
*/	

#include <cstdio>
#include <cstdlib>

using namespace std;

int f[22][22][22]={0};

int main()
{
	for ( int i = 1 ; i <= 20 ; ++ i )
		f[i][1][0] = f[i][i][0] = 1;
	for ( int i = 1 ; i <= 20 ; ++ i )
		for ( int j = 1 ; j < i ; ++ j ) {
			for ( int k = 0 ; k < 20 ; ++ k )
				f[i][j][k] = (i-j+1)*f[i-1][j-1][k]+j*f[i-1][j][k];
			for ( int k = 0 ; k < 20 ; ++ k )
				if ( f[i][j][k] > 99999 ) {
					f[i][j][k+1] += f[i][j][k]/100000;
					f[i][j][k]    = f[i][j][k]%100000;
				}
		}
		
	freopen("k.in","r",stdin);
	freopen("k.out","w",stdout);
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF) {
		int end = 20;
		while ( end > 0 && !f[n][m][end] ) -- end;
		printf("%d",f[n][m][end --]);
		while ( end >= 0 ) printf("%0.5d",f[n][m][end --]);
		printf("\n");
	}
	return 0;
}