permutation(递推).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>

int t[110][110];
bool num[110];
int p[110];
int c[110][110];
int t2[110][110];

void CAL()
{
    int i,j,k,l;
    
    t[1][0] = 1;
    
    c[0][0] = 1;
    c[1][0] = 1;
    c[1][1] = 1;
    for (i=2;i<=100;i++) {
        c[i][0] =1;
        for (j=1;j<=i;j++) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % 2007;
        }
    }
    
    for (k=2;k<=100;k++) {
        for (l=0;l<=k-1;l++) {
            if (l==0) {
                for (i=0;i<=k-1;i++) {
                    t[k][i+1] += t[k-1][i];
                    t[k][i+1] %= 2007;
                }
                continue;
            }
			if (l==k-1) {
				for (i=0;i<=k-1;i++) {
					t[k][i] += t[k-1][i];
                    t[k][i] %= 2007;
				}
				continue;
			}
            for (i=0;i<=k-l-2;i++) {
                for (j=0;j<=l-1;j++) {
                    t[k][i+j+1] += ((t[k-l-1][i] * c[k-1][l]) % 2007) * t[l][j];
                    t[k][i+j+1] %= 2007;
                }
            }
        }
    }
}

void cal2()
{
    int i,j;
    t2[1][0] = 1;
    for (i=2;i<=100;i++) {
        t2[i][0] = 1;
        for (j=1;j<i;j++) {
            t2[i][j] = t2[i-1][j-1]*(i-j) + t2[i-1][j]*(j+1);
            t2[i][j] %= 2007;
        }
    }
}

int main()
{
    int n,k;
    //CAL();//answer in t
    cal2();//answer in t2
    while (scanf("%d %d",&n,&k)==2) {
        printf("%d\n",t2[n][k]);
    }
}