Wannafly挑战赛18-序列

时间限制: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)

输出描述:

一个整数 表示答案模109+7

示例1

输入

5
输出

7

解题思路:
整体来看,a[x] = a[x-1] [1, -2, 0.5],那么等于从n-1个[1,-2,0.5]中选出n-1个数值相乘(a[x-1]=a[x-2] [1,-2,0.5]同理化简式子),
最后答案要是1,所以-2就必须有偶数个,同理0.5的个数要等于-2.顺序无关.
那所有的转换中,就只要保证有若干组(-2,-2,0.5,0.5)存在

表达式表示偶数个2的个数与偶数个0.5的个数组合;组合数用二项式系数,杨辉三角来求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
long long c[maxn][maxn];

int main(){
for(int i = 0; i < maxn; i++){//杨辉三角
c[i][0] = 1;
c[i][i] = 1;
for(int j = 1; j < i; j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
int n;
while(~scanf("%d", &n)){
n--;
long long ans = 0;
for(int i = 0; i*2 <= n; i += 2){
ans = (ans%mod + (c[n][i]*c[n-i][i])%mod)%mod;
}
printf("%lld\n", ans);
}
return 0;
}

点击查看
欢迎关注公众号,感谢支持 !
0%