国际大学生程序设计竞赛例题_3.4排列

1,题意:
n个数,n!中排列组合.
如:1,2,3 可以1<2<3  2<3>1
问:给定一个n和k,问k个小于号的组合有多少种.
2,解决:
显然f(1,0)=0;求f(n,k)
(1)n-1长度,有k个,加入最大值,放在最左边,<数不变.放在<连接的两个数之间也不变,3<5 3<8>5
这样增加到f(n-1,k)*(k+1)个.
(2)n-1长度,有k-1个,加入最大值,放在最右边,<数加1,放在>连接的两个数之间加1,5>3 5<8>3
增加到f(n-1,k-1)*(n-1-k+1)
得到:f(n,k)=f(n-1,k)*(k+1)+f(n-1,k-1)*(n-k).
3,实现代码:

#include <iostream>
using namespace std;

const int MAXN=101;
int f[MAXN][MAXN];

int main()
{
    freopen("3.4.in","r",stdin);
    memset(f,0,sizeof(f));
    f[0][0]=1;
    int n,k;
    for(int n=1;n<MAXN;n++)
        for(int k=0;k<n;k++)
        {
            if(k==0)
                f[n][k]=f[n-1][k]*(k+1);
            else
                f[n][k]=( f[n-1][k]*(k+1)+f[n-1][k-1]*(n-k) )%2007;
        }
    while(cin>>n>>k)
        cout<<f[n][k]<<endl;
    return 0;
}