Oiclass PU2TI P3791 棋子题解

思维

我们可以优先考虑以下的三情况：

• 1 2 3 此时我们会发现 1 和 2 挡住了 3 ，那么此时 1 和 2 必然将先死一个。
• 1 3 5 此时我们会发现所有棋子都可以先死，因此方案数为棋子数的全排列数，即其阶乘。
• 1 2 4 此时 1 和 2 挡住了 4 ，只要 1 或 2 先死一个，那么后面的就可以按照方案二的情况来计算。

因此我们可以考虑维护一个像方案二一样的 1 3 5 7 9 ... 的序列，然后统计答案。

我们可以将答案分为两种情况统计：

• \(a_i = 2i\) ，此时我们要让前一个先挂掉，然后序列不变
• \(a_i \ne 2i\) ，此时统计方案数

AC Code :

#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

int n, ans = 1, a[100009];

signed main() {
    cin >> n;
    if (n == 1) {
        cout << 1;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int last = 1, cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] != last + 1) {
            last += 2;
            cnt += 1;
        } else {
            ans = ans * (cnt + 1) % 1000000007;
        }
    }
    for (int i = 1; i <= cnt; i++) {
        ans = ans * i %  1000000007;
    }
    cout << ans;
}