论多测不清空,oi见祖宗的泛用性
我的代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int mod=998244353;
int a[N][N];
int n,m,c,f;
int lens[N][N],down[N][N];
void init(){
memset(lens,0,sizeof(lens));
memset(down,0,sizeof(down));
memset(a,0,sizeof(a));
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _T,id;
cin>>_T>>id;
while(_T--){
init();
cin>>n>>m>>c>>f;
a[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char inpu;
cin>>inpu;
if(i==1)a[i-1][j]=1;
if(j==1)a[i][j-1]=1;
a[i][j]=inpu-'0';
}
}
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
int x=a[i][j]^1;
if(x==0)continue;
lens[i][j]=x;
lens[i][j]+=lens[i][j+1];
down[i][j]=x;
down[i][j]+=down[i+1][j];
}
}
int ansc=0,ansf=0;
for(int j=1;j<m;j++){
int cntc=0;//c当前总数
int prel=0,cntl=0;
//上方总合法行 可计入答案列数
int cntf=0;
for(int i=1;i<=n;i++){
if(a[i][j]==1){
prel=cntl=0;
continue;
}
int tmp=cntl*(lens[i][j]-1);
tmp%=mod;
ansc+=tmp,ansc%=mod;
ansf+=cntf,ansf%=mod;
cntf+=tmp,cntf%=mod;
cntl+=max(0,lens[i-1][j]-1),cntl%=mod;
}
}
cout<<(ansc*c)%mod<<' '<<(ansf*f)%mod<<'\n';
}
return 0;
}
注意到ansf由cntf更新,但是在a[i][j]=1这个断开处我们并没有将cntf清零,因此要将
if(a[i][j]==1){
prel=cntl=0;
continue;
}
改为
if(a[i][j]==1){
prel=cntl=cntf=0;
continue;
}