上海计算机学会2024年10月赛C++丙组第5题构造排程

构造排列

内存容量限制为256 Mb，运行时间上限设定为1000 ms。

题目描述

给定一个整数 n ，请构造一个长度为 n 的排列 p1, p2, ..., pn ，使得在该排列中不出现任意三个参数 i, j, k 满足 i < j < k 且 pi < pj < pk 的情况。

请问对于给定的数值 n ，有多少个长度为 n 的排列能够满足上述条件。由于最终结果可能非常庞大，因此需要将答案对 10^9 + 7 取模后输出。

输入格式

输入内容为单行，包含一个正整数n

输出格式

输出一个符合规范的自然数，用以表达最终结果

数据范围

• 在数据占比为 30% 的情况下，n 的取值范围限定在 1 至 10 之间
  • 当数据占比达到 60% 时，n 的取值范围扩展至 1 至 100
  • 若采用全部数据进行处理，则 n 的取值范围将扩大至 1 至 10^4

样例数据展示

输入:
3
输出:
5
说明:
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1 均符合要求。
唯有 1,2,3 不符合既定条件。

解析：通过搜索方式能够处理约三成的数据，具体实现可参考相关代码：

 #include <bits/stdc++.h>