递推—构造字符串

待我称王封你为后i 2022-07-11 07:20 148阅读 0赞

Problem Description  
UMR 闲来无聊玩起了自己的名字，现在的她想知道对于给定的长度 n，只用自己的 ‘U’, ‘M’, ‘R’ 这 3 个字符最多能构成多少种不同的字符串。但是因为 UMR 并不喜欢 MM ，所以 MM 是不能连在一起的。

Input  
输入数据有多组（数据组数不超过 100000），到 EOF 结束。  
每组输入一个整数 n (1 <= n <= 100000)，表示 UMR 想要构成的字符串长度。

Output  
对于每组数据，输出一个整数，表示 UMR 只用 ‘U’, ‘M’, ‘R’ 这 3 个字符并且 MM 不能连在一起的最多能构成多少种不同的长度为 n 的字符串的个数（因为结果可能很大，请输出对 1000000007 取模之后的结果）。  
Example Input  
1  
2  
233

Example Output  
3  
8  
546261695

Hint  
用a\[n\]表示长度为n的方案数， 对于当前第n个数有3种情况：  
1、第n个数是U， 此时有a\[n-1\]种情况  
2、第n个数是R， 此时有a\[n-1\]种情况  
3、第n个数是M， 即第n-1个数只能是U或者R，  
此时有a\[n-2\]种情况  
Author  
「2017年寒假集训 结训赛1」UMR

#include <stdio.h>
    #define MAXN 100004
    #define mod 1000000007
    
    int main()
    {
        int x;
        long long a[MAXN];
        a[1] = 3;
        a[2] = 8;
        for(int i = 3; i <= 100000; i++)
        {
        
            a[i] = (a[i-1]*2 + a[i-2]*2)%mod;
        }
        while(scanf("%d", &x) != EOF)
        {
        
            printf("%lld\n", a[x]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 48ms
    Take Memory: 884KB
    Submit time: 2017-01-19 08:51:34
    ****************************************************/

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关递推与递归

递推 include <stdio.h> include <stdlib.h> int main(int argc, char argv[])

忘是亡心i/ 2022年12月12日 04:55/ 0 赞/ 206 阅读

相关 HDU 1165(递推)

题意：如题。题中 0<m<=3 参考别人推出一些公式： m=0时 A(m,n)=n+1; m=1时 A(m,n)=A(0,A(1,n-1))=A(1,n-1

左手的ㄟ右手/ 2022年09月20日 11:25/ 0 赞/ 142 阅读

相关 hdu 1165 递推

题目： As is known, Ackermann function plays an important role in the sphere of theoretica

喜欢ヅ旅行/ 2022年08月21日 04:28/ 0 赞/ 156 阅读

相关递推——数字矩阵

数字矩阵 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description

﹏ヽ暗。殇╰゛Y/ 2022年07月13日 13:21/ 0 赞/ 179 阅读

相关递推—构造字符串

Problem Description UMR 闲来无聊玩起了自己的名字，现在的她想知道对于给定的长度 n，只用自己的 ‘U’, ‘M’, ‘R’ 这 3 个字符最多能构成

待我称王封你为后i/ 2022年07月11日 07:20/ 0 赞/ 149 阅读

相关养兔子递推

养兔子 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statistic][St

雨点打透心脏的1/2处/ 2022年06月18日 12:48/ 0 赞/ 167 阅读

相关暗黑的字符串---递推公式

题目描述一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑

我会带着你远行/ 2022年06月09日 09:25/ 0 赞/ 170 阅读

相关黄金时代----递推

Problem Description 在古希腊时期，有一天毕达哥拉斯走在街上，在经过铁匠铺前他听到铁匠打铁的声音非常好听，于是驻足倾听。他发现铁匠打铁节奏很有规律，

阳光穿透心脏的1/2处/ 2022年05月16日 11:58/ 0 赞/ 224 阅读

相关 hdu4045(递推)

不会斯特林数的只能用递推思想了，结果发现推出来的就是斯特林数。。。 include <stdio.h> include <stdlib.h> incl

桃扇骨/ 2022年03月28日 07:50/ 0 赞/ 221 阅读

相关递推（二）：递推法的应用

下面通过一些典型实例及其扩展来讨论递推法的应用。【例2】骨牌铺方格在2×n的一个长方形方格中，用一种2×1的骨牌铺满方格。输入n（n<=40），

青旅半醒/ 2021年11月24日 00:22/ 0 赞/ 353 阅读