首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列

热度指数：3453 时间限制：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

输入

输出

说明

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

算法知识视频讲解

腌萝卜干

发表于 2026-02-01 10:38:41

分析定义, 的倍数的位置个数假设分配给的倍数位置是, 那么分配给非的倍数的位置就是那么得到等式得到那么答案等于个位置里面选择个位置是的倍数的位置里面还剩下个的倍数, 因为位置不是的倍数, 但是是的倍数, 因此整体也是的倍数个位置任意排列个位置任意排列代码实现 #incl 展开全文

pandaC222

发表于 2026-02-01 13:59:11

这是一道数学组合题，类似于高中排列组合那一章的一道题吧，只需要推出来式子我们知道我们需要ned=n/2个我们已经有cnt=n/3个满足条件还需要rem=ned-cnt个不满足条件的有n-cnt个我们需要交换已经满足条件的（即3的倍数）与不满足条件的进行交换每次交换会使满足条件的个数+1由此可知，我们展开全文

mollor

发表于 2026-02-01 00:54:02

本质数学题我们可以求出这个这个排列里面有x = n//3个3的倍数，我们需要y = n//2个3的倍数那么我们可以在x中选y - x个挪到外面，在外面n - x 个里面选y - x个放进来，然后里面的全排一下，外面的全排一下就好了喵这道题的难点全在求逆元和组合数上面了() #include<b 展开全文

牛客856751393号

发表于 2025-03-14 22:03:11

def ksm(a, b): # 快速幂计算 a ** b res = 1 while b: if b & 1: res = res * a % MOD a = a * a % MOD b > 展开全文

Turgen

发表于 2026-02-01 01:56:08

一个位置如果是有效的，那么要么位置是3的倍数，要么数字是3的倍数。记有个位置和数字是3的倍数。现在3的倍数已经产生了cnt 个有效计数。现在我们每分配一个3的位置给3的倍数，有效计数就不变，我们每分配一个3的位置给非3的倍数，有效计数就+1只需要保证最后的计数是即可。假设分了一一对应的位置给3的展开全文

牛客655678577号

发表于 2026-02-04 00:11:01

import sys MOD = 10**9 + 7 def precompute_factorials(n): fact = [1] * (n + 1) for i in range(1, n + 1): fact[i] = fact[i - 1] * i % 展开全文

野萌太君

发表于 2025-04-29 15:31:36

#include <stdio.h> int main() { int n; scanf("%d", &n); int num_triples, num_half; num_triples = n / 3; num_ 展开全文

YunBaichuan

发表于 2026-02-01 11:13:21

参考：https://blog.nowcoder.net/n/0fd8dbf5108c4ebda0ae48f8b43f3ba6 思路：组合数学，推式子。这种组合数学比较常用的就是fac预处理以及乘法逆元inv和comb的函数了，要写熟。然后就是数学过程的推式子了，令表示中有多少个位置是3的倍数，同时展开全文

greatofdream

发表于 2025-08-10 14:15:22

import sys n = int(input()) N = n // 3 n_2 = n // 2 MOD = 1000000007 def order(n0, n1): res = 1 for i in range(n0, n1, -1): res = (res 展开全文

AlL_VieW

发表于 2025-04-08 15:23:31

#include<bits/stdc++.h> #define int long long using namespace std; int const N = 1e6+9; int const mod = 1e9+7; int n; int f[N],nf[N]; int ksm(i 展开全文

问题信息

数论

难度：

8条回答 41收藏 336浏览

小红的好排列

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题