塔子哥是一个热爱编程的少年,他喜欢用 red
字符串来编写自己的程序。他认为 red
字符串是最美丽的字符串,因为它代表了热情、活力和创造力。他经常用 red
字符串来做各种有趣的实验,比如生成随机图案、加密解密信息、模拟物理现象等等。
有一天,塔子哥在网上看到了一个编程竞赛,要求参赛者用 red
字符串来完成一个复杂的任务。塔子哥很感兴趣,决定挑战自己。他下载了题目,发现是一个关于字符串权值的数学问题。塔子哥觉得这个问题很有意思,因为它可以测试他对 red
字符串的理解和掌握。
题目里给定了一个字符串的美丽度为:该字符串包含的 red
子序列的数量。(注意:子序列是可以不连续的),然后又给定了一个字符串的权值为:该字符串所有连续子串的美丽度之和。然后题目的问题是:长度为 n 的、仅由字符 r
、 e
、 d
构成的所有字符串(共有 3n 个字符串)的权值之和是多少?(答案请对 109+7 取模。)
现在塔子哥想知道这个题目怎么写,你能帮帮他吗?
第一行输入一个正整数 n 。( 1≤n≤1000 )
输出一个整数,表示长度为 n 的、仅由字符 r
、e
、 d
构成的所有字符串的权值之和。
输入
4
输出
18
提示
对于字符串rred , 它的子串是 {r,rr,rre,rred,r,re,red,e,ed,d},其中rred 的美丽值是 2 , red 美丽值是1。所以权值是2 + 1 = 3
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.