题解：P11742 Dynamic Mex Problem

· · 题解

出题人题解。

方法思路

我们可以轻松得出以下结论：

  1. 当 n 是偶数时：所有排列的 mex 值都是 0。这是因为每个排列中以序列最小值0作为最小值的子区间数总是偶数（因为一共有 i \times (n - i + 1) 个区间以序列最小值 0 为最小值，而 i 和 n - i + 1 之中一定有一个偶数），因此 0 不会出现在集合 S(a) 中，mex 值为 0，此时 mex=0 的方案数为 n!，其他为 0。

  2. 当 n 是奇数时：0 可能出现在集合 S(a) 中，也可能不出现。如果 0 出现，则 mex 值一定为 1 （就相当于把 a 分为了两个长度为偶数的序列，其中有一个包含 1，而根据上文，此时，1 一定不在 S(a) 中）。如果 0 不出现，则 mex 值为 0。具体来说：

    • 当 0 前面有偶数个数时，集合 S(a) 的 mex 值为 1。
    • 当 0 前面有奇数个数时，集合 S(a) 的 mex 值为 0。

    此时 mex=0 的方案数为\dfrac{(n-1)}{2}\times(n-1)!。mex=1 的方案数为\dfrac{n+1}{2}\times(n-1)!。其他为 0。

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

const int mod = 1e9 + 7;
int n;

signed main(){
    IOS;
    cin >> n;
    int ans = 1, las;
    for(int i = 1; i <= n; i++) las = ans, ans *= i, ans %= mod;
    if(n % 2 == 0){
        cout << ans << '\n';
        for(int i = 1; i <= n; i++) cout << 0 << '\n';
    }
    else{
        cout << (n - 1) / 2 * las % mod << '\n';
        cout << (n + 1) / 2 * las % mod << '\n';
        for(int i = 2; i <= n; i++) cout << 0 << '\n';
    }
    return 0;
}