一开始是想排列组合做的,排列组合感觉确实可以推出公式,但是复杂度嘛..
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]
1 #include2 #include 3 #include 4 5 #define SIGMA_SIZE 26 6 #pragma warning ( disable : 4996 ) 7 using namespace std; 8 9 inline int Max(int a,int b) { return a>b?a:b; }10 inline int Min(int a,int b) { return a>b?b:a; }11 const int inf = 0x3f3f3f3f;12 const int maxn = 1e3+5;13 const int mod = 10056;14 15 int n;16 int dp[maxn][maxn];17 long long sum[maxn];18 19 void init()20 {21 memset( dp, 0, sizeof(dp) );22 memset( sum, 0, sizeof(sum) );23 dp[0][0] = 1;24 }25 26 int main()27 {28 int all; cin >> all;29 int cnt = 1;30 31 init();32 for( int i = 1; i <= 1000; i++ )33 {34 long long s = 0;35 for ( int j = 1; j <= i; j++ )36 { dp[i][j] = (dp[i-1][j]+dp[i-1][j-1])%mod*j; s += dp[i][j]; s %= mod; }37 sum[i] = s;38 }39 40 while (all--)41 {42 int k; cin >> k;43 printf( "Case %d: %lld\n", cnt++, sum[k] );44 }45 return 0;46 }