RPG的错排

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long rcd[30];
int n;
void init()//初始化计数每个数的错排个数（即n个数每个都不在自己正确的位置上的种数）
{
    rcd[2]=1;
    rcd[3]=2;
    for(int i=4;i<=25;++i)
    rcd[i]=(rcd[i-1]+rcd[i-2])*(i-1);
}
int getc(int m,int k)
{
    int ans=m;
    for(int i=2;i<=k;++i)
    ans=ans*(m-i+1)/i;
    return ans;
}
void solve()
{
    if(n==1) cout<<1<<endl;
    else if(n==2) cout<<1<<endl;
    else if(n==3) cout<<1<<endl;
    else if(n==4) cout<<7<<endl;
    else{
        long long ans=0,m;
        if(n&1) m=(n>>1)+1;
        else m=n>>1;
        for(int i=m;i<n-1;++i){
            ans+=getc(n,i)*rcd[n-i];
        }
       cout<<ans+1<<endl;
    }

}
int main()
{
    std::ios::sync_with_stdio(false);
    init();
    while(scanf("%d",&n)&&n)
    solve();
}