原题链接：[http://47.121.118.174/p/618]
没人写题解我来水一篇()
注意到 $n,m$ 的取值范围，直接暴力枚举的时间复杂度是$O(n^3m^3)$会超时，所以考虑用前缀和做。
创建三个二维前缀和数组
$sumR,sumRO,sumROG，$
分别表示在$(1,1)$到$(i,j)$范围内
$R,RO,ROG$的数量。
大致的思路：遍历字符矩阵，前缀和数组先继承之前的数据
（二维前缀和模板:

$$sumR[i][j] = sumR[i-1][j]+sumR[i][j-1]-sumR[i-1][j-1];$$
），然后根据$a[i][j]$的值，对前缀和数组进行处理:
$$a[i][j]=='R'->sumR[i][j]++;$$ $$a[i][j]=='O'->sumRO[i][j]+=sumR[i][j]$$ $$a[i][j]=='G'->sumROG[i][j]+=sumRO[i][j]$$

Java代码如下：

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(st.nextToken()); 
        int m = Integer.parseInt(st.nextToken());
        char[][] a = new char[n+1][m+1];
        long[][] sumR = new long[n+1][m+1];
        long[][] sumRO = new long[n+1][m+1];
        long[][] sumROG = new long[n+1][m+1];
        for(int i = 1;i <= n;i++) {
        	StringBuilder sb = new StringBuilder(" "+br.readLine());
        	a[i] = sb.toString().toCharArray();
        }
        for(int i = 1;i <= n;i++) {
        	for(int j = 1;j <= m;j++) {
        		sumR[i][j] = sumR[i-1][j]+sumR[i][j-1]-sumR[i-1][j-1]+(a[i][j]=='R'?1:0);
        		sumRO[i][j] = sumRO[i-1][j]+sumRO[i][j-1]-sumRO[i-1][j-1]+(a[i][j]=='O'?sumR[i][j]:0);
        		sumROG[i][j] = sumROG[i-1][j]+sumROG[i][j-1]-sumROG[i-1][j-1]+(a[i][j]=='G'?sumRO[i][j]:0);
        	}
        }
        long ans = sumROG[n][m] % 998244353;
        pw.println(ans);
        pw.flush();
    }
}

题意简述

给定一个字符矩阵，统计矩阵中出现子串 ROG 的数量。

解题思路

本题使用二维前缀和的思想，方式记录每个位置处 R、RO、ROG 的数量，避免暴力遍历，将复杂度优化到 O(nm)。

总体逻辑

• R[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 R 的总个数。
• RO[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 RO 的总个数。
• ROG[i][j]：记录从左上角 (1,1) 到 (i,j) 区域内 ROG 的总个数。

C++代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 998244353;
const int N = 2005;
char a[N][N];	// 记录要输入的字符矩阵  
int R[N][N];	// 从(1,1)到(i,j)，出现了多少个"R"
int RO[N][N];	// 从(1,1)到(i,j)，出现了多少组"RO" 
int ROG[N][N];	// 从(1,1)到(i,j)，出现了多少组"ROG" 
int n, m;
string s;
int ans;

int funcRO( int i, int j ){	// 判断这个位置是不是"O" 
	if( a[i][j] == 'O' )
		return R[i][j];		// 当前是'O'，再加上之前的'R'的数量，就是当前有多少组"RO"
	return 0;
}
int funcROG( int i, int j ){ // 判断这个位置是不是"G"
	if( a[i][j] == 'G' )
		return RO[i][j];	// 当前是'G'，再加上之前的'RO'的数量，就是当前有多少组"ROG"
	return 0;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0); 
	cin >> n >> m;
	for( int i = 1; i <= n; i++ ){
		cin >> s;
		s = " " + s;	// 将字符串中的每一个字符存入字符矩阵a的对应位置 (最好从下标 1 开始) 
		for( int j = 1; j <= m; j++ ){
			a[i][j] = s[j];	// 字符串中的每一位放到二维字符数组这一行的每一位上  
		}
	}
	// 构建二维前缀和 
	for( int i = 1; i <= n; i++ ){
		for( int j = 1; j <= m; j++ ){
			// 枚举到每一个位置时，前缀和中都要记入数据    
			R[i][j] = R[i-1][j] + R[i][j-1] - R[i-1][j-1] + (a[i][j] == 'R');
			RO[i][j] = RO[i-1][j] + RO[i][j-1] - RO[i-1][j-1] + funcRO( i, j );
			ROG[i][j] = ROG[i-1][j] + ROG[i][j-1] - ROG[i-1][j-1] + funcROG( i, j );
		}
	}
	// ROG[n][m]就是从(1,1)到(n,m)出出现了多少组"ROG" 
	ans = ROG[n][m] % MOD;
	cout << ans;
	return 0;
}

import sys
input = lambda:sys.stdin.readline().strip()
n,m = map(int, input().split())
MD=998244353
s1 = [[0] * (m+1) for _ in range(n+1)]
s2 = [[0] * (m+1) for _ in range(n+1)]
s3 = [[0] * (m+1) for _ in range(n+1)]
def acc(x, y):
    for m in [s1,s2,s3]:
        m[x+1][y+1] = m[x][y+1] + m[x+1][y] - m[x][y]
        m[x+1][y+1] %= MD
for i in range(n):
    inp = input()
    for j in range(m):
        acc(i, j)
        if inp[j] == 'R':
            s1[i+1][j+1] += 1
        elif inp[j] == 'O':
            s2[i+1][j+1] += s1[i+1][j+1]
        elif inp[j] == 'G':
            s3[i+1][j+1] += s2[i+1][j+1]
print(s3[n][m]%MD)

#include<bits/stdc++.h>
using namespace std;
#define int long long
/* 简单说一下本题思路：ROG 
   算法中对三这个数一定一定敏感
   思路：对每个位置的 R G计数--前缀和计数发起
         2再遍历全地图 找到O 此时计数 前面 (1,1)--(x,y)-R数  后面 (x,y)--(n,m)--G数  
   本质：前缀和计数 + 线性三元分析 
*/ 
const int mo=998244353; 
const int N=2003;
char a[N][N];
int sR[N][N];
int sG[N][N];
int n,m;
signed main()
{ std::ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	   cin>>a[i][j];
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 {
	   sR[i][j]=(a[i][j]=='R')+sR[i-1][j]+sR[i][j-1]-sR[i-1][j-1];
	   sG[i][j]=(a[i][j]=='G')+sG[i-1][j]+sG[i][j-1]-sG[i-1][j-1];	
	 }
	int ans=0;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	 { if(a[i][j]=='O')
	   {
	   int R=sR[i][j];
	   int G=sG[n][m]-sG[i-1][m]-sG[n][j-1]+sG[i-1][j-1];
	   ans=(ans%mo)+(R*G%mo);
	   ans%=mo;
       }
	 }
	cout<<ans<<"\n"; 
	return 0;
}