解决这道题首先要解决这个问题,给出一个排列P,至少需要交换(任意位置)几次才能变成自然排列,把这个排列P看成一个置换,分解成循环,目标是使的每个循环的长度为1,不难看出((= =!)),各个循环之间是不需要交换的,而一个循环长度为k的循环要分解成为长度为1的循环需要(k-1)次交换,所以结论为有k个循环组成的长度为n的序列共需要(n-k)次交换才能变为自然排列。有了结论,接着就是递推了,设table[i][j]表示长度为i的序列,需要至少j次交换变为自然的序列个数,递推式为:table[i][j]
= table[i-1][j]+table[i-1][j-1]*(i-1)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; typedef long long LL; typedef unsigned long long ULL; const int MAXN(25); ULL table[MAXN][MAXN]; int main() { table[1][0] = 1LL; for(int i = 2; i <= 21; ++i) { table[i][0] = 1LL; for(int j = 1; j < i; ++j) table[i][j] = table[i-1][j]+table[i-1][j-1]*(i-1); } int n, k; while(scanf("%d%d", &n, &k), n+k) { printf("%llu\n", table[n][k]); } return 0; }