UVa11077

dp+置换

可以把排列分成几个循环，然后dp统计

dp[i][j]=dp[i-1][j-1]*(i-1)+dp[i-1][j],表示当前有i个元素，至少换j次，然后如果不在自己应该在的位置有i-1种情况，在自己位置上有1种情况，转移即可

话说vjudge也有100AC了。。。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

const int N = ;

int n, k;

ull dp[N][N];

int main()

{

    dp[][] = ;

    for(int i = ; i < ; ++i)

        for(int j = ; j < ; ++j) dp[i][j] = (ull)(i - ) * dp[i - ][j - ] + dp[i - ][j];

    while(scanf("%d%d", &n, &k) && (n !=  || k != )) printf("%llu\n", dp[n][k]);

    return ;

}

巴特西

UVa11077

最新文章

热门文章