「牛客练习赛53A」超越学姐爱字符串

更好的阅读体验

Portal

Portal1: Nowcoder

Description

超越学姐非常喜欢自己的名字，以至于英文字母她只喜欢\(\textrm{"c"}\)和\(\textrm{"y"}\)。因此超越学姐喜欢只含有\(\textrm{"c"}\)和\(\textrm{"y"}\)的字符串，且字符串中不能出现两个连续的\(\textrm{"c"}\)。请你求出有多少种长度为\(n\)的字符串是超越学姐喜欢的字符串。答案对\(1e9 + 7\)取模。

Input

输入一个整数\(n\)。

\(1 \le n \le 100000\)。

Output

输出一个整数表示答案。

Sample Input

3

Sample Output

5

Sample Explain

Solution

我们通过枚举可以发现

当\(n = 1\)时，答案为\(2\)：c, y；

当\(n = 2\)时，答案为\(3\)：cy, yc, yy；

当\(n = 3\)时，答案为\(5\)：cyy, cyc, yyy, yyc, ycy；

当\(n = 4\)时，答案为\(8\)：yyyy, yyyc, yycy, ycyy, cyyy, cycy, yccy, ycyc；

当\(n = 5\)时，答案为\(13\)：yyyyy, yyyyc, yyycy, yycyy, ycyyy, cyyyy, yycyc, ycyyc, cyyyc, ycycy, cyycy, cycyy, cycyc；

\(\cdots \cdots\)

容易总结出规律：\(\textrm{f(i) = f(i - 1) + f(i - 2)}(x \ge 3)\)

在写完代码时，还需要对于\(n = 1\)时特判。

Code

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int n;

int main() {

    scanf("%d", &n);

    if (n == 1) {//特判n = 1的情况

        printf("2\n");

        return 0;

    }

    LL x1 = 2, x2 = 3;

    for (int i = 3; i <= n; i++) {

        LL tmp = x1;

        x1 = x2 % mod;

        x2 = (x2 + tmp) % mod;//前两项的和

    }

    printf("%lld\n", x2 % mod);//不要忘记取余

    return 0;

}