方法思路

1. 问题分析：题目要求统计所有包含"ab"子序列的子序列数目。关键在于如何高效计算这些子序列的数量，避免直接枚举所有可能的子序列。
2. 动态规划：使用动态规划来维护当前状态下的好子序列数目。定义dp[i]表示前i+1个字符中满足条件的子序列数目。
3. 状态转移：
   • 当遇到字符'a'时，当前字符可以单独使用或与之前的所有子序列组合，因此dp[i] = 2 * dp[i-1]。
   • 当遇到字符'b'时，当前字符可以与之前所有的'a'组合形成新的好子序列。此时需要计算新增的好子序列数目，即2^i - 2^b_count，其中b_count是之前遇到的'b'的数量。
4. 快速幂取模：由于子序列数目可能非常大，使用快速幂来计算2的幂次，并对结果取模以防止溢出。
5. 边界处理：处理字符串长度小于2的情况，直接返回0。

这种方法通过动态规划和数学推导，高效地统计了所有满足条件的子序列数目，确保在较大的输入规模下也能快速运行。

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    private static final long MOD = 1_000_000_007;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int len = s.length();
        
        // 边界条件处理
        if (len <= 1) {
            System.out.println(0);
            return;
        }
        
        long[] dp = new long[len];
        int flag = 0; // 记录已处理的 'b' 的数量
        
        // 初始化 dp[0] 和 dp[1]
        dp[0] = 0;
        if (s.charAt(0) == 'b') flag++;
        
        if (len >= 2) {
            dp[1] = (s.charAt(0) == 'a' && s.charAt(1) == 'b') ? 1 : 0;
            if (s.charAt(1) == 'b') flag++;
        }
        
        // 动态规划处理
        for (int i = 2; i < len; i++) {
            if (s.charAt(i) == 'a') {
                dp[i] = (2 * dp[i-1]) % MOD;
            } else if (s.charAt(i) == 'b') {
                // 关键计算：化简后的表达式
                long termI = powerMod(2, i);
                long termFlag = powerMod(2, flag);
                long diff = (termI - termFlag + MOD) % MOD; // 处理负数
                dp[i] = (dp[i-1] + diff) % MOD;
            }
            
            // 更新 flag
            if (s.charAt(i) == 'b') flag++;
        }
        
        System.out.println(dp[len-1]);
    }
    
    // 快速幂取模函数，避免溢出
    private static long powerMod(long base, long exp) {
        long result = 1;
        base %= MOD; // 确保基在模范围内
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return result;
    }
}

Python

def power_mod(base, exp, mod=10**9 + 7):
    """快速幂取模函数，避免溢出"""
    result = 1
    base %= mod  # 确保基在模范围内
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp //= 2
    return result

def main():
    MOD = 10**9 + 7
    s = input().strip()
    length = len(s)
    
    # 边界条件处理
    if length <= 1:
        print(0)
        return
    
    dp = [0] * length
    flag = 0  # 记录已处理的 'b' 的数量
    
    # 初始化 dp[0] 和 dp[1]
    dp[0] = 0
    if s[0] == 'b':
        flag += 1
    
    if length >= 2:
        dp[1] = 1 if s[0] == 'a' and s[1] == 'b' else 0
        if s[1] == 'b':
            flag += 1
    
    # 动态规划处理
    for i in range(2, length):
        if s[i] == 'a':
            dp[i] = (2 * dp[i-1]) % MOD
        elif s[i] == 'b':
            # 关键计算：化简后的表达式
            term_i = power_mod(2, i, MOD)
            term_flag = power_mod(2, flag, MOD)
            diff = (term_i - term_flag + MOD) % MOD  # 处理负数
            dp[i] = (dp[i-1] + diff) % MOD
        
        # 更新 flag
        if s[i] == 'b':
            flag += 1
    
    print(dp[length-1])

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 1e9 + 7;

// 快速幂取模函数
inline int power_mod(long long base, int exp) {
    long long result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    int n = s.size();
    
    // 边界条件处理
    if (n <= 1) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> dp(n);
    int b_count = 0; // 记录已处理的 'b' 的数量
    
    // 初始化
    dp[0] = 0;
    if (s[0] == 'b') b_count++;
    
    if (n >= 2) {
        dp[1] = (s[0] == 'a' && s[1] == 'b') ? 1 : 0;
        if (s[1] == 'b') b_count++;
    }
    
    // 优化后的动态规划处理
    for (int i = 2; i < n; i++) {
        if (s[i] == 'a') {
            dp[i] = (2LL * dp[i-1]) % MOD; // 使用2LL确保乘法使用long long
        } else { // s[i] == 'b'
            int term_i = power_mod(2, i);
            int term_flag = power_mod(2, b_count);
            int diff = (term_i - term_flag + MOD) % MOD;
            dp[i] = (dp[i-1] + diff) % MOD;
            b_count++;
        }
    }
    
    cout << dp[n-1] << endl;
    return 0;
}