如果你12pts
查看原帖
如果你12pts
1122611
stickman_stickmin楼主2024/11/19 17:20

多测不清空,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;
  }
2024/11/19 17:20
加载中...