解题思路

设最终听到的序列为字符串 $s$（仅含 L/R）。一次击打会产生 1 个或 2 个相同字母：

• 左鼓：产生 L 或 LL；右鼓：产生 R 或 RR。

观察可知：一次击打不会跨越字母种类边界，因此答案对每个由相同字符组成的连续段（run） 彼此独立，再把每段的方案数相乘即可。

对一个长度为 $k$ 的 L（或 R）连续段，我们要把它切分成若干块，每块长度只能是 1 或 2（分别代表一次击打发出 1 个或 2 个相同的声）。 这正是典型的 1/2 划分计数，令 $f[i]$ 表示长度为 $i$ 的连续段的切分方案数，则

因此 $f[i]=\text{Fib}(i+1)$。 于是整串的答案为：各连续段长度 $k$ 的 $f[k]$ 的乘积，对模 $10^9+7$ 取模。

实现要点（算法：RLE + DP（斐波那契））：

1. 预处理斐波那契（或上述 $f$）到所有测试用例中出现的最大串长（$\le 2\times 10^5$）。
2. 扫描 $s$，做一次游程编码（run-length encoding），每遇到一个连续段长度为 $k$，把答案乘上 $f[k]$。
3. 乘法取模。

复杂度分析

• 预处理：$O(N)$，其中 $N=\max |s|$（全体测试用例的最大长度，$\le 2\times 10^5$）。
• 逐例计算：线性扫描，每个字符只访问一次，总计 $O\!\left(\sum |s|\right)$。
• 空间复杂度：$O(N)$ 用于存储 $f$ 数组。

代码实现

Python

import sys

MOD = 10**9 + 7

def precompute_f(max_n):
    # f[i]: 长度为 i 的连续段（L 段或 R 段）的切分方案数
    f = [0] * (max_n + 2)
    f[0] = 1  # 空段 1 种
    f[1] = 1  # 长度 1 只能切成 [1]
    for i in range(2, max_n + 1):
        f[i] = (f[i-1] + f[i-2]) % MOD
    return f

def count_for_string(s, f):
    # 对字符串 s 做 RLE，并累乘对应的 f[len]
    n = len(s)
    ans = 1
    i = 0
    while i < n:
        j = i
        # 找到 s[i] 这一段的右端
        while j < n and s[j] == s[i]:
            j += 1
        run_len = j - i
        ans = (ans * f[run_len]) % MOD
        i = j
    return ans

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    strings = data[1:1+t]
    max_len = max(len(s) for s in strings) if t > 0 else 0
    f = precompute_f(max_len)
    out = []
    for s in strings:
        out.append(str(count_for_string(s, f)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;

    // 预处理 f 到 maxN
    static long[] precomputeF(int maxN) {
        long[] f = new long[maxN + 2];
        f[0] = 1; // 空段
        if (maxN >= 1) f[1] = 1; // 长度 1
        for (int i = 2; i <= maxN; i++) {
            f[i] = (f[i-1] + f[i-2]) % MOD;
        }
        return f;
    }

    // 计算单个 s 的答案
    static long solveOne(String s, long[] f) {
        long ans = 1;
        int n = s.length();
        int i = 0;
        while (i < n) {
            int j = i + 1;
            // 找到连续段 [i, j)
            while (j < n && s.charAt(j) == s.charAt(i)) j++;
            int len = j - i;
            ans = (ans * f[len]) % MOD;
            i = j;
        }
        return ans;
    }

    public static void main(String[] args) {
        // 数据总长 <= 2e5，用 Scanner 足够
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        String[] arr = new String[t];
        int maxLen = 0;
        for (int i = 0; i < t; i++) {
            arr[i] = sc.next();
            maxLen = Math.max(maxLen, arr[i].length());
        }
        long[] f = precomputeF(maxLen);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            sb.append(solveOne(arr[i], f)).append('\n');
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

// 预处理 f 到 maxN：f[0]=1, f[1]=1, f[i]=f[i-1]+f[i-2]
vector<long long> precomputeF(int maxN) {
    vector<long long> f(maxN + 2, 0);
    f[0] = 1;
    if (maxN >= 1) f[1] = 1;
    for (int i = 2; i <= maxN; ++i) {
        f[i] = (f[i-1] + f[i-2]) % MOD;
    }
    return f;
}

// 计算单个 s 的答案
long long solveOne(const string& s, const vector<long long>& f) {
    long long ans = 1;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        int j = i + 1;
        while (j < n && s[j] == s[i]) ++j; // 找到连续段 [i, j)
        int len = j - i;
        ans = (ans * f[len]) % MOD;
        i = j;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (!(cin >> t)) return 0;
    vector<string> strs(t);
    int maxLen = 0;
    for (int i = 0; i < t; ++i) {
        cin >> strs[i];
        maxLen = max(maxLen, (int)strs[i].size());
    }
    auto f = precomputeF(maxLen);

    for (int i = 0; i < t; ++i) {
        cout << solveOne(strs[i], f) << "\n";
    }
    return 0;
}

题目内容

在这个世界里，有左右两个大鼓。对左鼓的击打记为 "$L$"，对右鼓的击打记为 "$R$"。有趣的是，一次击打可能发出一次声音，也可能因为共鸣而发出两次相同的声音：

• 一次左鼓击打要么发出 "$L$"，要么发出 "$LL$"；
• 一次右鼓击打要么发出 "$R$"，要么发出 "$RR$"。

你只记录到了最终听到的声音序列s (仅由字符 '$L$' 和 '$R$' 组成)。请问，有多少种原始的击打序列 $p$ 能产生该声音序列？

输入描述

第一行包含一个整数 $t(1≤t≤10^5)$，表示测试用例数。 接下来 $t$ 行，每行包含一个非空字符串 $s$ ，由字符 '$L$' 和 '$R$' 组成，长度记为 $∣s∣$ 。 保证所有测试用例中 $∑∣s∣≤2×10^5$。

输出描述

对于每个测试用例，输出一行，包含一个整数——能产生该声音序列的击打序列总数。 由于答案可能很大，请对 $10^9+7$ 取模后输出。

样例1

输入

5
LR
LLRR
LRLR
L
RRR

输出

1
4
1
1
3

说明

LR:

• 左鼓击打一次发出 L，右鼓击打一次发出 R;
• 只有一种击打序列 LR。

LLRR:

• 左鼓击打一次发出 LL，右鼓击打一次发出 RR;
• 左鼓击打两次各发出 L，右鼓击打一次发出 RR;
• 左鼓击打一次发出 LL，右鼓击打两次各发出 R;
• 左鼓击打两次各发出 L，右鼓击打两次各发出 R;
• 共 4 种击打序列。

RRR:

• 右鼓击打一次发出 RR，右鼓击打一次发出 R;
• 右鼓击打一次发出 R，右鼓击打一次发出 RR;
• 右鼓击打三次各发出 R;
• 共 3 种击打序列。