首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列

热度指数：3454 时间限制：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\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

在一行上输入一个正偶数  代表排列中的元素数量。

输出描述:

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

输出

说明

在这个样例中，长度为  的排列有且仅有两个：
，第一个元素  使得 ，第二个元素  使得 ，均不是  的倍数；
，同理。
因此，长度为  的排列中，不存在好排列。

示例2

输入

输出

说明

在这个样例中，一共有  个长度为  的排列满足条件，例如：
，第一个元素  使得 ，第二个元素  使得 ，第三个元素  使得 ，第四个元素  使得 ，恰好有一半的  使得  是  的倍数。

算法知识视频讲解

Python3

Chinry

n=int(input())
MOD=10**9+7
def A(m,n):
    result=1
    for i in range(n-m+1,n+1):
        result=result*i % MOD
    return result
if n==2:
    print('0')
else:
    print(A(2*(n//3)-n//2,n//3)**2*A(n//2-n//3,n-n//3)*A(n-3*(n//3)+n//2,n-n//3)%MOD)

这题是真考数论，简化也是真的难简化。

大致思路拆解如下：

1、放在索引为3i位置的3x在全部3x中的组合：C(2*(n//3)-n//2 n//3)
2、放置3x数的3i索引在全部3i索引中的组合：C(2*(n//3)-n//2 n//3)
3、确定放置在3i索引的3x数（受1限制）在确定放置3x数的3i索引（受2限制）上的排列组合：A(2*(n//3)-n//2 2*(n//3)-n//2)
4、剩下的非3x的数字需要放置在剩下3i索引（受2限制）中的组合：C(n//2-n//3 n-n//3)
5、确定放在剩下3i索引（受2限制）的非3x数字（受4限制）在索引上的排列组合：A(n//2-n//3 n//2-n//3)
6、剩下所有数字（受1 4影响）直接进行排列组合：A(n-n//3 n-n//3)
六个乘起来就是了，然后化简到分母为1为止（也就是只有A存在）

发表于 2025-12-27 17:12:26 回复(0)

提交观点

问题信息

数论

难度：

1条回答 41收藏 342浏览

小红的好排列

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题