思路与算法

预处理每个0向右连续0的个数h（不含自己）和向下连续0数down（含自己）。逐列、按被1隔开的连续块扫描中间横臂所在行i，维护至少隔一行的上横臂h之和P。C图贡献P*h[i]，F图还乘可选竖直下端数down[i]-1。分别模998244353累加再乘c,f。

正确性说明

固定竖线列和两横臂行，上下横臂的右端可独立选，共h[top]*h[mid]种。顶横臂至少高两行，块内前缀P恰包含这些top且竖线全为0。C无需下段；F的竖线还须向下至少一格，有down[mid]-1种端点。每个图形由这些坐标唯一确定，扫描将所有合法图形计一次。

复杂度

含整表初始化与读入，每组O(nm)时间、O(nm)空间；总时间O(∑nm)。

易错点

横臂必须向右且正长度，上下横臂间至少一行。遇1重置竖直块前缀；c或f为0时对应答案0。

参考代码（C++11）

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

int main() {
    int T, id;
    cin >> T >> id;
    const long long MOD = 998244353;
    while (T--) {
        int n, m, c, f;
        cin >> n >> m >> c >> f;
        vector<string> a(n);
        for (auto &s : a)
            cin >> s;
        vector<vector<int>> right(n, vector<int>(m)), down = right;
        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--)
                if (a[i][j] == '0') {
                    right[i][j] = j + 1 < m && a[i][j + 1] == '0' ? right[i][j + 1] + 1 : 0;
                    down[i][j] = 1 + (i + 1 < n ? down[i + 1][j] : 0);
                }
        long long C = 0, F = 0;
        for (int j = 0; j < m; j++) {
            long long sum = 0;
            int begin = 0;
            for (int i = 0; i < n; i++) {
                if (a[i][j] == '1') {
                    sum = 0;
                    begin = i + 1;
                    continue;
                }
                if (i - 2 >= begin)
                    sum = (sum + right[i - 2][j]) % MOD;
                long long ways = sum * right[i][j] % MOD;
                C = (C + ways) % MOD;
                F = (F + ways * (down[i][j] - 1)) % MOD;
            }
        }
        cout << c * C % MOD << " " << f * F % MOD << "\n";
    }
}