自动搬运

查看原文

来自洛谷，原作者为

	LFL **

搬运于2025-08-24 23:09:53，当前版本为作者最后更新于2025-02-14 19:09:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人题解。

方法思路

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

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