简要题意
\(T\) 组数据，给你一个 \(n\times m\) 的 \(01\) 矩阵。 \(0\) 部分可以组成 \(A_c\) 个 \(\texttt{C}\) 型图案和 \(A_f\) 个 \(\texttt{F}\) 型图案。你需要输出 \(A_c \times c \bmod 998244353,A_f \times f \bmod 998244353\)。
\(1\leq T \leq 5,1 \leq n,m \leq 10^3,c\in\{0,1\},f\in\{0,1\}\)
思路
纪念考场手切的 NOIP T1。
预处理 \(r_{i,j},d_{i,j}\) 表示向右、向下 \(0\) 可以延申到多少格以外。如：
0010
0000
0001
1010
0111
其中 \(r_{2,2}=2,d_{2,2}=2\).
首先考虑 \(\texttt{C}\) 型图案。由上面一横，中间一竖，下面一横组成。考虑枚举左上角 \((i,j)\)，那么以这个点为左上角的 \(C\) 型图案就可以求出来了：
\[\sum_{k=i+2}^{i+d_{i,j}}r_{i,j}r_{k,j} \]解释：左下角为 \((i,k)\)。下限加 \(2\) 因为竖长最少为 \(1\)。求和的式子运用了乘法原理。
\(F\) 型图案只比 \(C\) 多了下面那一竖。我们也可以方便的推出式子：
\[\sum_{k=i+2}^{i+d_{i,j}}r_{i,j}r_{k,j}d_{k,j} \]这样子暴力算是 \(O(Tn^2m)\) 的，可以获得 \(85\) 分。
考虑优化，上面两个式子把 \(r_{i,j}\) 提出来后直接前缀和优化即可。
这样子时间复杂度是 \(O(Tnm)\)，可以通过本题。
代码
// O(nmt)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,id,n,m,c,f;
int a[1005][1005];
char s[1005];
int rgt[1005][1005],down[1005][1005];
int rdqzh[1005][1005],rgtqzh[1005][1005];
const int mod = 998244353;
inline int M(int x){
return (x%mod+mod)%mod;
}
inline void getrgt(){
for(int i=1;i<=n;i++){
int j=1;
while(j<=m){
if(a[i][j]==0){
int start=j;
for(;j<=m&&a[i][j]==0;j++);
for(int val=0,k=j-1;k>=start;k--,val++){
rgt[i][k]=val;
}
j--;
}
j++;
}
}
}
inline void getdown(){
for(int i=1;i<=m;i++){
int j=1;
while(j<=n){
if(a[j][i]==0){
int start=j;
for(;j<=n&&a[j][i]==0;j++);
for(int val=0,k=j-1;k>=start;k--,val++){
down[k][i]=val;
}
j--;
}
j++;
}
}
}
inline void preworks(){
getrgt();
getdown();
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
// rgtqzh[i][j] is rgt[1][j]+rgt[2][j]+...+rgt[i][j]
rgtqzh[i][j]=M(rgtqzh[i-1][j]+rgt[i][j]);
// rdqzh[i][j] is rgt[1][j]*down[1][j]+rgt[2][j]*down[2][j]+...+rgt[i][j]**down[i][j]
rdqzh[i][j]=M(rdqzh[i-1][j]+M(rgt[i][j]*down[i][j]));
}
}
}
inline int countc(){
int ans=0;
for(int i=1;i<=m;i++){// C's col
for(int j=1;j<=(n-2);j++){ // C's top row
if((j+2)>(j+down[j][i]))continue;
ans = M(ans+M(rgt[j][i]*M(rgtqzh[j+down[j][i]][i]-rgtqzh[j+2-1][i])));
// int pans=0;
// for(int k=j+2;k<=(j+down[j][i]);k++){// C's bottom row
// pans=pans+(rgt[k][i])%mod;
// pans%=mod;
// }
// ans=ans+pans*rgt[j][i]%mod;
}
}
return ans;
}
inline int countf(){
int ans=0;
for(int i=1;i<=m;i++){// F's col
for(int j=1;j<=(n-3);j++){// F's top row
if((j+2)>(j+down[j][i]))continue;
ans=M(ans+M(rgt[j][i]*M(rdqzh[j+down[j][i]][i]-rdqzh[j+2-1][i])));
// for(int k=(j+2);k<=(j+down[j][i]);k++){// F's bottom row
// ans=ans+(((rgt[j][i]*rgt[k][i])%mod)*down[k][i])%mod;
// ans%=mod;
// }
}
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifndef ZYBAKIOI
freopen("plant.in","r",stdin);
freopen("plant.out","w",stdout);
#endif
cin>>t>>id;
if(id==1){
while(t--)cout<<0<<' '<<0<<'\n';
return 0;
}
while(t--){
memset(rgt,0,sizeof(rgt));
memset(down,0,sizeof(down));
memset(rdqzh,0,sizeof(rdqzh));
memset(rgtqzh,0,sizeof(rgtqzh));
memset(a,0,sizeof(a));
cin>>n>>m>>c>>f;
for(int i=1;i<=n;i++){
cin>>(s+1);
for(int j=1;j<=m;j++){
a[i][j]=s[j]-'0';
}
}
preworks();
cout<<(c*countc())<<' '<<(f*countf())<<'\n';
}
return 0;
}
/*
I hope my grandfathers can give me a good prize in NOIP 2022.
ZYB,YSC,LF,LWX,HZY,ZBZ,YTXY,GRZ,LGS,DZY,WQX
they are my grandfathers,they AKed IOI!(%%%)
And They AK NOIP!
*/