首页 > 代码库 > HDU 2583 permutation

HDU 2583 permutation

2024-07-18 18:51:13   220人阅读

permutation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 167    Accepted Submission(s): 96

Problem Description
Permutation plays a very important role in Combinatorics. For example ,1 2 3 4 5 and 1 3 5 4 2 are both 5-permutations. As everyone‘s known, the number of n-permutations is n!. According to their magnitude relatives ,if we insert the sumbols "<" or ">"between every pairs of consecutive numbers of a permutations,we can get the permutations with symbols. For example,1 2 3 4 5 can be changed to 1<2<3<4<5, 1 3 5 4 2 can be changed to 1<3<5>4>2. Now it‘s yout task to calculate the number of n-permutations with k"<"symbol. Maybe you don‘t like large numbers ,so you should just geve the result mod 2009.
 
Input
Input may contai multiple test cases.
Each test case is a line contains two integers n and k .0<n<=100 and 0<=k<=100.
The input will terminated by EOF.
 
Output
The nonegative integer result mod 2007 on a line.
 
Sample Input
5 2
 
Sample Output
66
 
题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2583
 1 #include<stdio.h> 2 int main() 3 { 4       int n,k; 5       int dp[102][102]; 6       for(int i=0;i<=101;i++)   7       {   8         dp[i][0]=1;  dp[0][i]=0;   9       }  10     for(int i=1;i<=101;i++)11       for(int j=1;j<=101;j++)12       {13           if(i-j==1)    dp[i][j]=1;14           else if(i-j>1)    dp[i][j]=( dp[i-1][j]*(j+1) + dp[i-1][j-1]*(i-j) ) % 2009;15           else dp[i][j]=0;    16       }17     while(scanf("%d%d",&n,&k)!=EOF) 18     {19         printf("%d\n",dp[n][k]);20     }     21 }22 /*状态转移是:23 DP（n，k）=dp（n-1，k）*（k+1）+dp（n-1）（k-1）*（n-k）24 n代表考虑n个数字的状态，k代表小于号的个数。25 先作特殊情况，序列1 2 3 4 5 6，一共5个小于号，如果我要加入数字7，那么我有7种加法，并且只有一种加法会使小于号+1.26 序列a1 a2 a3 a4 a5 ……a(n-1)，一共有n-1个数字，有k个小于号，那么我加入an有n种加法，27 其中会使小于号+1的有n-k种（就是加在大于号的位置上），其他的k+1种不会改变小于号的个数。28 */

 


联系
我们