首页 > 试题广场 >

小红的双生排列

[编程题]小红的双生排列

热度指数：3655 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小红定义一个排列是双生排列，当且仅当任意相邻两项之和均为奇数。
$\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

输入

输出

说明

在这个样例中，长度为  的排列有：
  且为双生排列；
 ；
 ；
 ；
 ；
  且为双生排列。

算法知识视频讲解

pypy3

一个毕业生a

#排列组合问题，奇偶分开排列
#N为奇数，奇数只能放在前面，所以直接奇数的排列乘以偶数的排列就是答案
#N为偶数时，奇偶都可以放在前面，所以答案等于上面的情况乘以2
#这里取模比较麻烦不能自己写阶乘函数了，用math库里的函数直接输出阶乘取模
#乘法的取模算法可以去网上搜一下
import math

n =  int(input())
#计算奇偶数的数量
if n%2 == 0:
    qishu_c = n//2
    oushu_c = n//2
else:
    qishu_c = n//2 + 1
    oushu_c = n//2
#这里答案应该是n为奇数时，阶乘一（qishu_c）乘上阶乘二 （oushu_c）；N为偶数时，乘二就可以了 
#这里答案过于大，进行乘法的取模操作 
M = 10**9+7
res1 = math.factorial(qishu_c)%M
res2 = math.factorial(oushu_c)%M

if n % 2 == 0:
    res = res1 * res2 % M
    print((res*2)%M)
else:
    res = res1 * res2 % M
    print(res)

发表于 2025-04-14 22:05:48 回复(0)