原始问题:
计算首尾字符相同子序列的数量:Java代码实现与模运算优化
以下是使用Java代码实现的解决方案:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
int result = countSubsequences(str);
System.out.println(result);
}
public static int countSubsequences(String str) {
int mod = 998244353;
int[] dp = new int[26];
int[] prev = new int[26];
int n = str.length();
int result = 0;
for (int i = 0; i < n; i++) {
int index = str.charAt(i) - 'a';
dp[index] = (2 * prev[index] + 1) % mod;
prev[index] = (prev[index] + dp[index]) % mod;
}
for (int i = 0; i < 26; i++) {
result = (result + dp[i]) % mod;
}
return result;
}
}这段代码中,我们使用动态规划的思想来解决问题。我们定义两个数组dp和prev,分别用来记录当前字符结尾的子序列数量和上一个字符结尾的子序列数量。
我们遍历字符串中的每个字符,对于每个字符,我们计算以该字符结尾的子序列数量。具体计算方法如下:
- 首先,我们根据当前字符的ASCII码值计算出对应的索引
index。 - 然后,我们更新
dp[index]的值,根据上一个字符结尾的子序列数量prev[index]计算得到。具体计算方法为dp[index] = (2 * prev[index] + 1) % mod,其中mod为取模的值。 - 最后,我们更新
prev[index]的值,将其更新为prev[index] + dp[index]。
最后,我们遍历dp数组,将所有元素相加并对mod取模,得到满足条件的子序列的数量。
注意:由于题目要求对结果取模,所以在计算过程中需要注意取模的位置,以避免整数溢出。
Prev:Java代码实现:有一个n×m 的矩阵,要求从这个矩阵中选择出一个正方形,使得正方形中的数之和与剩下的数之和的差值绝对值尽可能小