0%

牛客16732 序列(排列组合)

链接:https://ac.nowcoder.com/acm/problem/16732
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

有一个长度为n的序列a,已知a[1]=a[n]=1,且对于2 <= x <= n,a[x] / a[x-1]是以下三个数字之一 [ 1,-2,0.5 ],问有多少种不同的序列满足题意。
两个序列不同当且仅当它们有至少一个位置上的数字不同,序列a可以为任何实数。

输入描述:

一个整数 表示n (1<= n <= 1e3)

输出描述:

一个整数 表示答案模 10^9^ +7

在这里插入图片描述
直接整体来看,a[x] = a[x-1]*[1, -2, 0.5],那么等于选出n-1个数值相乘

最后答案要是1,所以-2就必须有偶数个,同理0.5的个数要等于-2,顺序无关

1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())

import math
MOD = 1000000007
def c(m, n):
return math.factorial(m) // math.factorial(n) // math.factorial(m - n) % MOD
ans = 0
i = 0
num = n-1
while i <= num // 2:
ans = (ans + c(num, i) * c(num - i, i)) % MOD
i += 2
print(ans)
-------------    本文结束  感谢您的阅读    -------------