首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列
  • 热度指数：2187 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红认为一个偶数长度为 n 的排列 \{a_1,a_2,\dots,a_n\} 是好排列，当且仅当恰好有一半的 i 使得 a_i \times i 是 3 的倍数。
\hspace{15pt}小红想知道，全部长度为 n 的排列中，共有多少个好排列？由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

\hspace{15pt}长度为 n 的排列是由 1 \sim n 这 n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，\{2,3,1,5,4\} 是一个长度为 5 的排列，而 \{1,2,2\} 和 \{1,3,4\} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:
\hspace{15pt}在一行上输入一个正偶数 n \left(2 \leqq n \leqq 10^6\right) 代表排列中的元素数量。


输出描述:
\hspace{15pt}输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

2

输出

0

说明

\hspace{15pt}在这个样例中，长度为 2 的排列有且仅有两个：
\hspace{23pt}\bullet\,\{1,2\}，第一个元素 1 使得 1 \times 1 = 1，第二个元素 2 使得 2 \times 2 = 4，均不是 3 的倍数；
\hspace{23pt}\bullet\,\{2,1\}，同理。
\hspace{15pt}因此，长度为 2 的排列中，不存在好排列。
示例2

输入

4

输出

18

说明

\hspace{15pt}在这个样例中，一共有 18 个长度为 4 的排列满足条件，例如：
\hspace{23pt}\bullet\,\{1,2,4,3\}，第一个元素 1 使得 1 \times 1 = 1，第二个元素 2 使得 2 \times 2 = 4，第三个元素 4 使得 4 \times 3 = 12，第四个元素 3 使得 3 \times 4 = 12，恰好有一半的 i 使得 a_i \times i 是 3 的倍数。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

数论
难度：
0条回答 243浏览

热门推荐

相关试题

小红的好排列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号