题解说明

问题背景： 给定 $n$ 个仅由字符 $L$ 与 $R$ 构成的字符串。对每个字符串 $s$，分别进行“从左向右扫描”和“从右向左扫描”的动态规划，得到四组计数数组：$L[i][k]$、$R[i][k]$（左扫），$L2[i][k]$、$R2[i][k]$（右扫）。然后对每一对字符串 $(i,j)$ 计算匹配结果：$\sum_{k} \big( L[i][k]\cdot L2[j][k] + R[i][k]\cdot R2[j][k] \big)$，并对模数 $M=10^9+7$ 取模输出。

核心思路： $1.$ 左扫 DP（计算 $L[i][k]$、$R[i][k]$）：

• 设字符串长度为 $m$。维护数组 $p[0..m]$ 与 $q[0..m]$，初始 $p[0]=1$、其余为 $0$。
• 扫描每个字符：
  • 若为 $L$：对所有 $k$，执行 $p[k]\leftarrow p[k-1]+q[k-1]$（下标合法时），表示向“左层”推进。
  • 若为 $R$：对所有 $k$，执行 $q[k]\leftarrow p[k+1]+q[k+1]$，表示向“右层”推进。
• 扫描结束后，令 $L[i][k]=p[k]$，$R[i][k]=q[k]$，并对 $M$ 取模。

$2.$ 右扫 DP（计算 $L2[i][k]$、$R2[i][k]$）：

• 重新置 $p$、$q$ 为 $0$，设 $q[0]=1$。从右向左扫描：
  • 若为 $L$：对所有 $k$，进行 $p[k-1]\leftarrow p[k-1]+p[k]$、$q[k-1]\leftarrow q[k-1]+p[k]$，并清零 $p[k]$。
  • 若为 $R$：对所有 $k$，进行 $p[k+1]\leftarrow p[k+1]+q[k]$、$q[k+1]\leftarrow q[k+1]+q[k]$，并清零 $q[k]$。
• 扫描结束后，令 $L2[i][k]=p[k]$，$R2[i][k]=q[k]$，并对 $M$ 取模。

$3.$ 跨字符串匹配与累加：

• 对每一对 $(i,j)$，计算
  $\displaystyle ans=\sum_{k=0}^{N-1}\big(L[i][k]\cdot L2[j][k]+R[i][k]\cdot R2[j][k]\big)\bmod M$，并输出。
• 其中常量 $N=3000+5$ 为上界数组维度，保证所有 $k$ 范围覆盖；取模 $M=10^9+7$ 防止溢出。

直觉理解：

• $p[k]$、$q[k]$ 可视为在层级 $k$ 上的计数，$L$ 将质量向“左”转移，$R$ 将质量向“右”转移；从两端扫描得到两套独立累积。
• 两字符串 $(i,j)$ 的匹配在同一层级 $k$ 上做点对点乘加，从而结合左右两端的推进影响。

复杂度分析：

• 单字符串 DP 为 $O(m^2)$（每字符对 $k$ 的遍历），整体约 $O\big(\sum m^2\big)$。
• 配对求和为 $O(n^2\cdot N)$。对于输入上界 $N$ 与实际字符串长度适中时可接受。

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

// 定义常量：取模值M和数组最大维度N
const int M = 1e9 + 7, N = 605;

// 定义存储中间计算结果的二维数组
// L[i][k]和R[i][k]：第i个字符串从左向右扫描的结果
// L2[i][k]和R2[i][k]：第i个字符串从右向左扫描的结果
long long L[N][N], R[N][N], L2[N][N], R2[N][N];

int main() {
    ios::sync_with_stdio(false);  // 关闭输入输出同步，加快速度
    int n;
    cin >> n;  // 输入字符串的数量

    // 处理每个字符串，计算其对应的L、R、L2、R2数组
    for (int id = 1; id <= n; ++id) {
        string s;
        cin >> s;  // 输入当前字符串
        int m = s.size();  // 获取字符串长度
        
        // p和q数组用于动态规划计算
        vector<long long> p(m + 1), q(m + 1);
        p[0] = 1;  // 初始化左扫的起始状态

        // 从左向右扫描字符串，计算L和R数组
        for (char c : s) {
            if (c == 'L') {
                // 当遇到'L'时，更新p数组（向左移动相关的状态）
                for (int k = m; k; --k) {
                    p[k] = (p[k - 1] + q[k - 1]) % M;
                }
            } else {
                // 当遇到'R'时，更新q数组（向右移动相关的状态）
                for (int k = 0; k < m; ++k) {
                    q[k] = (p[k + 1] + q[k + 1]) % M;
                }
            }
        }

        // 将计算结果保存到L和R数组中
        for (int k = 0; k <= m; ++k) {
            L[id][k] = p[k];
            R[id][k] = q[k];
        }

        // 重置p和q数组，准备进行右扫计算
        fill(p.begin(), p.end(), 0);
        fill(q.begin(), q.end(), 0);
        q[0] = 1;  // 初始化右扫的起始状态

        // 从右向左扫描字符串，计算L2和R2数组
        for (int i = m; i; --i) {
            if (s[i - 1] == 'L') {
                // 处理'L'字符，更新p和q数组
                for (int k = 1; k <= m; ++k) {
                    p[k - 1] = (p[k - 1] + p[k]) % M;
                    q[k - 1] = (q[k - 1] + p[k]) % M;
                    p[k] = 0;
                }
            } else {
                // 处理'R'字符，更新p和q数组
                for (int k = m - 1; k >= 0; --k) {
                    p[k + 1] = (p[k + 1] + q[k]) % M;
                    q[k + 1] = (q[k + 1] + q[k]) % M;
                    q[k] = 0;
                }
            }
        }

        // 将计算结果保存到L2和R2数组中
        for (int k = 0; k <= m; ++k) {
            L2[id][k] = p[k];
            R2[id][k] = q[k];
        }
    }

    // 计算并输出所有字符串对(i,j)的匹配结果
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            long long ans = 0;

            // 累加所有可能k值下的匹配结果，取模确保不溢出
            for (int k = 0; k < N; ++k) {
                ans = (ans + L[i][k] * L2[j][k] + R[i][k] * R2[j][k]) % M;
            }

            // 输出结果，控制格式
            cout << ans << (j == n ? '\n' : ' ');
        }
    }

    return 0;
}