首页 > 试题广场 >

小红的好排列

[编程题]小红的好排列

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

输入描述:

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

输出描述:

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

示例1

输入

输出

说明

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

示例2

输入

输出

说明

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

算法知识视频讲解

牛客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 > 展开全文

野萌太君

发表于 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_ 展开全文

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 展开全文

番禺小韭菜

发表于 2025-03-05 23:00:37

#include <iostream> using namespace std; const int MOD = 1e9 + 7; const int MAX = 1e6 + 5; long long fact[MAX], inv_fact[MAX]; // 快速幂取模 long 展开全文

hojiahao

发表于 2025-03-07 12:52:28

#include <iostream> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; // 模数 const int N = 1000010; // n的最大值加一些余量 LL fact[N], 展开全文

在努力存钱的懒羊羊很想去大厂

发表于 2025-08-08 11:25:21

import java.util.Scanner; public class Main { static long mod = 1000000007; public static void main(String[] args) { Scanner in = n 展开全文

Goldminer

发表于 2025-04-28 12:57:25

#include <iostream> using namespace std; int main() { int n; cin >> n; // 计算 3 的倍数的个数 int num_triples = n / 3; // 1 到 n 展开全文

问题信息

数论

难度：

6条回答 33收藏 244浏览

小红的好排列

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题