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;
}