2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务 他喜欢 R 字符，因
2023-09-07：用go语言编写。塔子哥最近在处理一些字符串相关的任务
他喜欢 R 字符，因为在某些任务中，这个字符通常表示“正确”的结果
另一方面，他不喜欢 B 字符，因为在某些任务中，这个字符通常表示“错误”的结果
为了解决他的任务，塔子哥定义了字符串的权值为字符串中 R 字符的出现次数
例如，对于字符串 BBRBRB，它的权值为 2，因为其中有 2 个 R 字符
现在，塔子哥面临一个问题，他有一个长度为 n 的字符串 s，它仅由 R 和 B 组成
他想知道，长度为 n 的仅由 R 和 B组成的字符串中，
字典序不小于 s 的字符串的权值之和是多少？
因此，他需要编写一个程序来解决这个问题
输入第一行为一个整数 n ，表示字符串的长度
输入第二行为一个长度为 n 的字符串 s ，字符串中元素组成仅为 R 和 B
输出一个整数，代表长度为 n 的、字典序不小于 s 的字符串权值之和。
输入样例：
3
RBR
输出：
7
解释：共有 3 个字符串字典序大于等于"RBR"，RBR权值为2，RRB为2，RRR为3。
1 <= n <= 100000，
结果可能很大，对1000000007取模。
来自[左程云](https://b23.tv/Zho7gh0)。
答案2023-09-07：
# 大体过程如下：
算法一（sum1）：
1.定义函数sum1，它接收一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串中权值之和。
2.在sum1中，定义了辅助函数process1，它通过递归生成所有可能的字符串，并计算符合条件的字符串的权值之和。
3.在process1中，递归地生成新字符串，每次添加'R'或'B'，直到生成的字符串长度与给定字符串长度相等。
4.如果生成的字符串与给定字符串相等或更大，返回权值之和，其中权值为'R'的个数。
5.如果生成的字符串小于给定字符串，返回0，表示没有符合条件的字符串。
6.在每个递归步骤中，将递归调用的结果相加，计算出所有可能字符串的权值之和。
7.在sum1函数中，调用process1函数并返回最终的权值之和。
算法二（sum3）：
1.定义函数sum3，它接受一个字符串作为参数，并返回字典序不小于该字符串的所有可能字符串的权值之和。
2.在sum3中，首先初始化一些辅助数组和变量。
3.使用动态规划的方法来计算权值之和。
4.创建一个长度为n+1的dp数组，其中dp[i]表示以第i个字符作为起始字符的后缀字符串的权值之和。
5.初始化dp[n]为给定字符串最后一个字符的权值。
6.从右到左遍历字符串，计算dp数组的值。
7.如果当前字符是'R'，根据公式计算p1和p2，然后将p1和p2相加得到dp[i]。
8.如果当前字符是'B'，将dp[i+1]的值赋给dp[i]。
9.最后返回dp[0]作为最终的权值之和。
时间复杂度：
- 算法一（sum1）的时间复杂度为O(2^n)，其中n是给定字符串的长度。因为它通过递归的方式生成所有可能的字符串。
- 算法二（sum3）的时间复杂度为O(n)，其中n是给定字符串的长度。因为它使用动态规划计算权值之和。
额外空间复杂度：
- 算法一（sum1）的额外空间复杂度为O(n)，因为递归调用process1函数可能会使用到O(n)的栈空间。
- 算法二（sum3）的额外空间复杂度为O(n)，因为它使用了dp数组来存储中间结果，数组长度为n+1。
# go完整代码如下：
```go
package main
import (
"fmt"
"math/rand"
"strings"
"time"
)
const MAXN = 100001
const mod = 1000000007
var pow2, f [MAXN]int
func sum1(str string) int {
return process1("", str)
}
func process1(path, s string) int {
if len(path) == len(s) {
if strings.Compare(path, s) >= 0 {
ans := 0
for i := 0; i < len(path); i++ {
if path[i] == 'R' {
ans++
}
}
return ans
} else {
return 0
}
} else {
return process1(path+"R", s) + process1(path+"B", s)
}
}
func initialize() {
pow2[0] = 1
for i := 1; i < MAXN; i++ {
pow2[i] = (pow2[i-1] * 2) % mod
}
f[1] = 1
for i := 2; i < MAXN; i++ {
f[i] = (pow2[i-1] + f[i-1]) % mod
f[i] = (f[i] + f[i-1]) % mod
}
}
func sum2(str string) int {
n := len(str)
s := []byte(str)
rnumber := make([]int, n)
rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
for i := 1; i < n; i++ {
rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
}
return process2(s, rnumber, n, 0)
}
func process2(s []byte, rnumber []int, n, i int) int {
var ans int
if i == n {
ans = rnumber[n-1]
} else {
if s[i] == 'B' {
p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
p2 := process2(s, rnumber, n, i+1)
ans = (p1 + p2) % mod
} else {
ans = process2(s, rnumber, n, i+1)
}
}
return ans
}
func sum3(str string) int {
n := len(str)
s := []byte(str)
rnumber := make([]int, n)
rnumber[0] = map[bool]int{true: 1, false: 0}[s[0] == 'R']
for i := 1; i < n; i++ {
rnumber[i] = rnumber[i-1] + map[bool]int{true: 1, false: 0}[s[i] == 'R']
}
dp := make([]int, n+1)
dp[n] = rnumber[n-1]
for i := n - 1; i >= 0; i-- {
if s[i] == 'B' {
p1 := int(((int64(rnumber[i]+1)*int64(pow2[n-i-1]))%int64(mod) + int64(f[n-i-1])) % int64(mod))
p2 := dp[i+1]
dp[i] = (p1 + p2) % mod
} else {
dp[i] = dp[i+1]
}
}
return dp[0]
}
func randomString(n int) string {
s := make([]byte, n)
for i := 0; i < n; i++ {
if rand.Float32() < 0.5 {
s[i] = 'B'
} else {
s[i] = 'R'
}
}
return string(s)
}
func main() {
rand.Seed(time.Now().UnixMilli())
N := 15
testTimes := 10000
fmt.Println("测试开始")
initialize()
for i := 0; i < testTimes; i++ {
n := rand.Intn(N) + 1
s := randomString(n)
ans1 := sum1(s)
ans3 := sum3(s)
if ans1 != ans3 {
fmt.Println("出错了!")
}
}
fmt.Println("测试结束")
}
```
# c++完整代码如下：
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <random>
constexpr int MAXN = 100001;
constexpr int mod = 1000000007;
std::vector<int> pow2(MAXN);
std::vector<int> f(MAXN);
int process1(const std::string& path, const std::string& s);
int sum1(const std::string& str) {
return process1("", str);
}
int process1(const std::string& path, const std::string& s) {
if (path.length() == s.length()) {
if (path.compare(s) >= 0) {
int ans = 0;
for (int i = 0; i < path.length(); i++) {
if (path[i] == 'R') {
ans++;
}
}
return ans;
}
else {
return 0;
}
}
else {
return process1(path + "R", s) + process1(path + "B", s);
}
}
void initialize() {
pow2[0] = 1;
for (int i = 1; i < MAXN; i++) {
pow2[i] = (pow2[i - 1] * 2) % mod;
}
f[1] = 1;
for (int i = 2; i < MAXN; i++) {
f[i] = (pow2[i - 1] + f[i - 1]) % mod;
f[i] = (f[i] + f[i - 1]) % mod;
}
}
int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i);
int sum2(const std::string& str) {
int n = str.length();
std::vector<char> s(str.begin(), str.end());
std::vector<int> rnumber(n);
rnumber[0] = (s[0] == 'R') ? 1 : 0;
for (int i = 1; i < n; i++) {
rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
}
return process2(s, rnumber, n, 0);
}
int process2(const std::vector<char>& s, const std::vector<int>& rnumber, int n, int i) {
int ans;
if (i == n) {
ans = rnumber[n - 1];
}
else {
if (s[i] == 'B') {
int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
int p2 = process2(s, rnumber, n, i + 1);
ans = (p1 + p2) % mod;
}
else {
ans = process2(s, rnumber, n, i + 1);
}
}
return ans;
}
int sum3(const std::string& str) {
int n = str.length();
std::vector<char> s(str.begin(), str.end());
std::vector<int> rnumber(n);
rnumber[0] = (s[0] == 'R') ? 1 : 0;
for (int i = 1; i < n; i++) {
rnumber[i] = rnumber[i - 1] + ((s[i] == 'R') ? 1 : 0);
}
std::vector<int> dp(n + 1);
dp[n] = rnumber[n - 1];
for (int i = n - 1; i >= 0; i--) {
if (s[i] == 'B') {
int p1 = (((int64_t)(rnumber[i] + 1) * (int64_t)pow2[n - i - 1]) % (int64_t)mod + (int64_t)f[n - i - 1]) % (int64_t)mod;
int p2 = dp[i + 1];
dp[i] = (p1 + p2) % mod;
}
else {
dp[i] = dp[i + 1];
}
}
return dp[0];
}
std::string randomString(int n) {
std::string s(n, ' ');
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 1);
for (int i = 0; i < n; i++) {
if (dis(gen) < 0.5) {
s[i] = 'B';
}
else {
s[i] = 'R';
}
}
return s;
}
int main() {
std::random_device rd;
std::mt19937 gen(rd());
int N = 15;
int testTimes = 100;
std::cout << "测试开始" << std::endl;
initialize();
for (int i = 0; i < testTimes; i++) {
int n = gen() % N + 1;
std::string s = randomString(n);
int ans1 = sum1(s);
int ans3 = sum3(s);
if (ans1 != ans3) {
std::cout << "出错了!" << std::endl;
}
}
std::cout << "测试结束" << std::endl;
return 0;
}
```
