题解 | 小红的双生排列

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
int n;

ll dfs(ll x)//计算阶乘的 DFS 函数
{
    ll res = 1;
    for(ll i=2; i<=x; i++) res = (res * i) % MOD;
    return res;
}
int main()
{
    cin >> n;
    if(n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    ll odd = (n+1)/2,even = n/2;//分别表示奇数部分和偶数部分的数量
    ll ans = 0;
    if(n%2 == 0)//当n为偶数时，排列模式有2种（奇偶交替或偶奇交替）
    {
        ans = 2 * dfs(odd) % MOD;
        //这个公式用于计算当 n 为偶数时，排列模式的数量。因为当 n 为偶数时，排列模式有两种：奇数在前偶数在后，或者偶数在前奇数在后。所以需要将奇数排列的数量乘以 2。
        ans = ans * dfs(even) % MOD;
        //这个公式用于计算当 n 为偶数时，最终的排列数量。在前面已经计算出奇数排列的数量并乘以 2 之后，这里再与偶数排列的数量相乘，得到总的排列模式数量。

    }else {//当n为奇数时，只能以奇数开头（因为奇数比偶数多1个）
        ans = dfs(odd) * dfs(even) % MOD;
        // 这个公式用于计算当 n 为奇数时，排列模式的数量。因为当 n 为奇数时，排列模式只能是奇数在前偶数在后，所以只需将奇数排列的数量与偶数排列的数量相乘即可。
    }
    cout << ans << endl;
    //dfs(1);
    return 0;
}
//1 2 2 8 12 72 144 1152 2304
//1 2 3 4 5  6  7   8    9