题意：

给定$n$和$k$，问有多少排列交换$k$次能变成升序

$n \le 21$

---

 

$uva$貌似挂掉了$vjudge$上一直排队

从某个排列到$1,2,...,n$和从$1,2,...,n$到某个排列是一样的

排列就是置换，分解循环，然后显然每个循环变成升序需要$len-1$次交换

然后有$t$个循环的置换需要$n-t$次交换

$DP$就行了$f[i][j]$表示前$i$个数有$j$个循环

其实可以发现就是第一类$stirling$数

注意：以后一定要测一遍极限会爆$long\ long$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=30;typedef unsigned long long ll;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,k;ll f[N][N];void dp(){    f[0][0]=1;    for(int i=1;i<=21;i++)        for(int j=1;j<=21;j++)            f[i][j]=f[i-1][j-1]+f[i-1][j]*(i-1);}int main(){    //freopen("in","r",stdin);    dp();    while(true){        n=read();k=read();        if(n==0&&k==0) break;        printf("%llu\n",f[n][n-k]);    }}