algorithm-class/算法周更班/class_2023_05_2_week/Code02_LexicographicBiggerSumOfR.java

package class_2023_05_2_week;

// 来自学员问题，来自真实笔试
// 塔子哥最近在处理一些字符串相关的任务
// 他喜欢 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://www.mashibing.com/question/detail/67223
public class Code02_LexicographicBiggerSumOfR {

	// 为了测试
	// 暴力方法
	public static int sum1(String str) {
		return process1("", str);
	}

	// 为了测试
	// 暴力方法
	public static int process1(String path, String s) {
		if (path.length() == s.length()) {
			if (path.compareTo(s) >= 0) {
				int ans = 0;
				for (int i = 0; i < path.length(); i++) {
					if (path.charAt(i) == 'R') {
						ans++;
					}
				}
				return ans;
			} else {
				return 0;
			}
		} else {
			return process1(path + "R", s) + process1(path + "B", s);
		}
	}

	// 以下为正式方法
	public static int MAXN = 100001;

	// pow2[i] : 长度为i的所有RB串，一共有多少字符串，%mod的余数
	// 一定要求余数！
	public static int[] pow2 = new int[MAXN];

	// f[i] : 长度为i的所有RB串，一共有多少权值和，%mod的余数
	// 一定要求余数！
	public static int[] f = new int[MAXN];

	public static int mod = 1000000007;

	static {
		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++) {
			// 2^i-1 + 2*f[i-1]
			f[i] = (pow2[i - 1] + f[i - 1]) % mod;
			f[i] = (f[i] + f[i - 1]) % mod;
		}
	}

	// 普通递归版
	// 不是最优解，但是展示了大过程
	public static int sum2(String str) {
		int n = str.length();
		char[] s = str.toCharArray();
		int[] rnumber = new int[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);
	}

	// 你依次填写字符串
	// 0...i-1范围上，你填写的东西，和s完全一样
	// 当前来到i位置，一共的长度是n
	// rnumber[i] : s[0...i]范围上有几个R
	// 返回 : 在[0...i-1]和s完全一样的情况下，后续所有字典序不小于s的字符串，整体的权值和是多少?
	public static int process2(char[] s, int[] rnumber, int n, int i) {
		int ans = 0;
		if (i == n) {
			ans = rnumber[n - 1];
		} else {
			if (s[i] == 'B') {
				// s当前位置是'B'，你可以填写R，也可以是B
				// 如果你当前填R，现在的情况是：
				// 0...i-1位置上你填写的和s一样；
				// i位置上s是'B'，你填写的是'R'；
				// i之后的剩余长度是 : n-i-1，你可以随便填了
				// n-i-1可以随便填，那么字符串个数为 : 2^(n-i-1)个
				// 这2^(n-i-1)个字符串，都是:
				// [0...i-1]和s一样，i位置比s多一个R，
				// 权值和 = 1) + 2)
				// 1) 是这2^(n-i-1)个字符串，前缀上的权值和
				// 2) 是这2^(n-i-1)个字符串，后缀上的权值和
				// 具体来说 :
				// 1) (s的[0...i]范围上R的数量 + 1) * 2^(n-i-1)
				// 2) 在[i+1....]范围上的权值和 : f[n-i-1]
				int p1 = (int) (((long) (rnumber[i] + 1) * pow2[n - i - 1]) % mod);
				p1 = (p1 + f[n - i - 1]) % mod;
				// 如果你当前填B，那么继续递归
				int p2 = process2(s, rnumber, n, i + 1);
				ans = (p1 + p2) % mod;
			} else {
				// s当前位置是'R'，你只能填写R，然后继续递归
				ans = process2(s, rnumber, n, i + 1);
			}
		}
		return ans;
	}

	// 彻底动态规划版
	// 正式版，时间复杂度O(N)
	public static int sum3(String str) {
		int n = str.length();
		char[] s = str.toCharArray();
		int[] rnumber = new int[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);
		}
		int[] dp = new int[n + 1];
		dp[n] = rnumber[n - 1];
		for (int i = n - 1; i >= 0; i--) {
			if (s[i] == 'B') {
				int p1 = (int) (((long) (rnumber[i] + 1) * pow2[n - i - 1]) % mod);
				p1 = (p1 + f[n - i - 1]) % mod;
				int p2 = dp[i + 1];
				dp[i] = (p1 + p2) % mod;
			} else {
				dp[i] = dp[i + 1];
			}
		}
		return dp[0];
	}

	// 为了测试
	public static String randomString(int n) {
		char[] s = new char[n];
		for (int i = 0; i < n; i++) {
			s[i] = Math.random() < 0.5 ? 'B' : 'R';
		}
		return String.valueOf(s);
	}

	public static void main(String[] args) {
		int N = 15;
		int testTimes = 10000;
		System.out.println("测试开始");
		for (int i = 0; i < testTimes; i++) {
			int n = (int) (Math.random() * N) + 1;
			String s = randomString(n);
			int ans1 = sum1(s);
			int ans3 = sum3(s);
			if (ans1 != ans3) {
				System.out.println("出错了!");
			}
		}
		System.out.println("测试结束");
	}

}