一开始是想排列组合做的,排列组合感觉确实可以推出公式,但是复杂度嘛..
dp[i][j]表示有i只马,j个名次的方法数,显然j<=i,然后递推公式就很好写了,一只马新加进来要么与任意一个名次的马并行,则加进来后仍有j种名次,且有j个名次可选择,所以新增j*dp[i-1][j]种;要么这匹马插进j-1名次中并变成总共j种名次,所以原来应有j-1种名次,在j-1种名次中有j种插法,所以新增j*dp[i-1][j-1]
#include <iostream>
#include <string.h>
#include <cstdio> #define SIGMA_SIZE 26
#pragma warning ( disable : 4996 )
using namespace std; inline int Max(int a,int b) { return a>b?a:b; }
inline int Min(int a,int b) { return a>b?b:a; }
const int inf = 0x3f3f3f3f;
const int maxn = 1e3+;
const int mod = ; int n;
int dp[maxn][maxn];
long long sum[maxn]; void init()
{
memset( dp, , sizeof(dp) );
memset( sum, , sizeof(sum) );
dp[][] = ;
} int main()
{
int all; cin >> all;
int cnt = ; init();
for( int i = ; i <= ; i++ )
{
long long s = ;
for ( int j = ; j <= i; j++ )
{ dp[i][j] = (dp[i-][j]+dp[i-][j-])%mod*j; s += dp[i][j]; s %= mod; }
sum[i] = s;
} while (all--)
{
int k; cin >> k;
printf( "Case %d: %lld\n", cnt++, sum[k] );
}
return ;
}