RPG的錯排

​​RPG的錯排​​

直接利用錯排公式進行求解

這裡需要注意的問題是，組合數不能夠打表算，因為會爆 long long

組合數計算方法：

temp=1;
for(int j=1;j<=i;++j)
    temp=temp*(n-j+1);
for(int j=1;j<=i;++j)
    temp/=j;      

另外需要注意的是如果要表示全部猜對的話，需要在最後加上 1，因為錯排公式中 ​

​sum[0]=0​

​

代碼：

// Created by CAD on 2019/8/15.
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll sum[30],c[30],ans,temp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    c[0]=c[1]=1,c[2]=2;
    sum[0]=sum[1]=0,sum[2]=1;
    for(int i=3;i<=25;++i)
        sum[i]=(i-1)*(sum[i-1]+sum[i-2]);
    int n;
    while(cin>>n&&n!=0)
    {
        ans=0;
        for(int i=n/2;i>=1;--i)
        {
            temp=1;
            for(int j=1;j<=i;++j)
                temp=temp*(n-j+1);
            for(int j=1;j<=i;++j)
                temp/=j;
            ans+=sum[i]*temp;
        }
        cout<<ans+1<<endl;
    }
    return 0;
}