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

This article was last modified days ago. The content of this post may be outdated!

Portal

Description

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

Input

输入一个整数$n$。

$1 \le n \le 100000$。

Output

输出一个整数表示答案。

Sample Input

Sample Output

Sample Explain

$\textrm{cyy, cyc, yyy, yyc, ycy}$。

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;
}

Article License: CC BY-NC-ND 4.0
Article Author: XiaoHuang

题解

C++ 动态规划找规律 Nowcoder