题解 | 小红的双生排列

水题，注意到题目说的条件：相邻两数之和为奇数，那么最终构造的双生数组应该是，“奇偶奇偶...”交错排列的。因此我们直接分奇偶讨论即可。

当 n 为奇数时，奇数数量比偶数数量多1，因此奇数只能放在奇数位置，偶数只能放到偶数位置，答案为 (n / 2)! * ((n + 1) / 2)!

当 n 为偶数时，奇数数量等于偶数数量，因此奇数位置有两种情况，答案应为 (n / 2)! * (n / 2)! * 2

#include<bits/stdc++.h>
using i64 = long long;

constexpr int M = 1e9 + 7;
i64 fac(i64 n) {
    i64 ans = 1;
    for (int i = 1; i <= n; i++) {
        (ans *= i) %= M;
    }
    return ans;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    i64 n;
    std::cin >> n;
    if (n & 1)
        std::cout << fac(n / 2) * fac((n + 1) / 2) % M;
    else 
        std::cout << fac(n / 2) * fac(n / 2) % M * 2 % M;

    return 0;
}
// 64 位输出请用 printf("%lld")

https://www.nowcoder.com/discuss/727521113110073344