NOIP2022 T1

· · 题解

一个不懂dp蒟蒻的题解

（前置知识：递推，乘法原理）

首先，预处理出对于每一个位置 (i，j) 向右和向下分别有多少个 0
并用数组 H[i][j] 、 S[i][j] 记下
具体实现（以向右为例）：
1.由于直接数的话比较麻烦，我们可以倒着数
2.用一个变量 v 存从右到当前位置时 0 的个数，遇到 1 则清零 

for (int i = 1; i <= n; i ++ ) {  //枚举行
            int v = 0;
            for (int j = m; j >= 1; j -- ) {  //倒着数
                if (ma[i][j] == '1') {v=0;continue;}
                if (v) H[i][j] = v;
                v ++;
            }
        }

此时对于样例1：

1 0
4 3 1 1
001
010
000
000

有 H 数组：

100
000
210
210

接着，开始计数
第一个想法：
1.枚举 \texttt{C} 的左上角 (i1，j1) ，若合法，则向下枚举左下角 （i2，j2） ，若合法，则计算 \texttt{C} 的个数 = H[i1][j1] H[i2][j2]
2.对于每一个 \texttt{C} ，若其左下角 (i2，j2) 下面有零（即 S[i2][j2] > 0）, 则计算 \texttt{F} 的个数 = H[i1][j1] H[i2][j2] * S[i2][j2]
时间复杂度 O(n^2m) ，会TLE

第二个想法：
可以发现， \texttt{C} 的左下角 （i2，j2） 会被枚举多次，因此，我们可以从下往上计数，记下位置 （i，j） 下面的所有位置向右的 0 的个数之和，用数组 qzh 记下，qzh[i][j] = qzh[i - 1][j] + H[i][j]，遇到合法的 \texttt{C} 的左上角 （i1，j1） 时就计算 \texttt{C} 的个数 = H[i1][j1] qzh[i1+2][j1]
但是，此时我们难以通过 \texttt{C} 求出 \texttt{F} 的个数，因为当枚举到合法的左上角时我们不知道已记录的左下角向下有几个 0
因此，我们再开一个 qzs 数组，记下向右和向下 0 的个数之积， qzs[i][j] = qzs[i - 1][j] + H[i][j] S[i][j] ，此时 \texttt{F} 的个数 = H[i][j] * qz2[i+2][j]
时间复杂度 O(nm)

代码

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;

const int N = 1e3 + 20; const LL MOD = 998244353;
char ma[N][N];
LL H[N][N], S[N][N];
LL qzh[N][N], qzs[N][N];  // 开longlong防止溢出 

int n, m, t, id; LL c, f;

int main () {
    scanf ("%d%d", &t, &id);
    while (t -- ) {
        memset (H, 0, sizeof (H));  memset (S, 0, sizeof (S));
        memset (qzh, 0, sizeof (qzh)); memset (qzs, 0, sizeof (qzs));
        LL ans1, ans2;  ans1 = ans2 = 0;
        scanf ("%d%d%lld%lld", &n, &m, &c, &f);
        for (int i = 1; i <= n; i ++ ) scanf ("%s", ma[i] + 1); // 下标从1开始 
        for (int i = 1; i <= n; i ++ ) {
            int v = 0;
            for (int j = m; j >= 1; j -- ) {
                if (ma[i][j] == '1') {v=0;continue;}
                if (v) H[i][j] = v;
                v ++;
            }
        }
        for (int i = 1; i <= m; i ++ ) {
            int v = 0;
            for (int j = n; j >= 1; j -- ) {
                if (ma[j][i] == '1') {v=0;continue;}
                if (v) S[j][i] = v;
                v ++;
            }
        }
        for (int i = 1; i <= m; i ++ ) 
            for (int j = n; j >= 1; j -- ) {
                if (ma[j][i] == '1') {qzh[j + 1][i] = 0;qzs[j + 1][i] = 0;continue;}
                // 清零，由于继续向上只会访问到j+1的位置，只需修改qz1[j+1][i] 
                ans1 = (qzh[j + 2][i] * H[j][i] % MOD + ans1) % MOD;
                ans2 = (qzs[j + 2][i] * H[j][i] % MOD + ans2) % MOD;
                // 更新qzh和qzs 
                qzh[j][i] = H[j][i] + qzh[j + 1][i];
                qzs[j][i] = (H[j][i] * S[j][i] % MOD + qzs[j + 1][i]) % MOD;
            }
        printf ("%lld %lld\n", c * ans1, f * ans2);
    }
    return 0;
}