P8865 [NOIP2022] 种花

P8865 [NOIP2022] 种花

 

#include <bits/stdc++.h>
using namespace std;const int mod = 998244353,maxn = 1e3 + 10;
int a[maxn][maxn],down[maxn][maxn],r[maxn][maxn],up[maxn][maxn];int main(){int T,id;cin >> T >> id;while(T--){int n,m,c,f;cin >> n >> m >> c >> f;memset(a,0,sizeof(a));memset(down,0,sizeof(down));memset(r,0,sizeof(r));memset(up,0,sizeof(up));for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){char ch; cin >> ch;if(ch=='1') a[i][j] = 1;//表示有土坑 
            }} for(int i = n; i >= 1;i--){for(int j = 1; j <= m; j++){if(a[i][j] == 0) down[i][j] = down[i + 1][j] + 1;}}for(int i = 1; i <= n; i++){for(int j = m; j >= 1;j--){if(a[i][j] == 0) r[i][j] = r[i][j + 1] + 1;}}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(a[i][j]==0){up[i][j] = r[i][j] - 1;up[i][j] += up[i - 1][j]; } }}long long cntc = 0,cntf = 0;for(int i = 3; i <= n; i++){for(int j = 1;j < m; j++){if(a[i][j] == 0 && a[i - 1][j] == 0){cntc = (cntc + up[i - 2][j] * r[i][j + 1]) % mod;cntf = (cntf + 1ll * up[i - 2][j] * r[i][j + 1] * down[i + 1][j]) % mod;}}}cout << cntc * c % mod << " " << cntf * f % mod << endl;}return 0;
}