1 条题解

  • 0
    @ 2024-3-28 21:25:05
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define int long long
    using namespace std;
    inline int read(){
    	int sum=0,f=1;char ch=getchar();
    	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
    	return sum*f;
    }
    int sum[505][505];
    int t[2500070],tt[2500070];
    int n,x,ans;
    signed main(){
    	n=read();
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			int x;
    			x=read();
    			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    		
    			for(int k=1;k<=i;k++){
    				for(int l=1;l<=j;l++){
    					int tmp=sum[i][j]-sum[k-1][j]-sum[i][l-1]+sum[k-1][l-1];
    					t[tmp]++;
    				}
    			}
    			for(int k=i+1;k<=n;k++){
    				for(int l=j+1;l<=n;l++){
    					int tmp=sum[k][l]-sum[i][l]-sum[k][j]+sum[i][j];
    					if(t[tmp]){
    						ans-=t[tmp]*tt[tmp];
    						tt[tmp]++;
    						ans+=t[tmp]*tt[tmp];
    					}
    				}
    			}
    		
    			for(int k=1;k<=i;k++){
    				for(int l=1;l<=j;l++){
    					int tmp=sum[i][j]-sum[k-1][j]-sum[i][l-1]+sum[k-1][l-1];
    					t[tmp]--;
    				}
    			}
    			for(int k=i+1;k<=n;k++){
    				for(int l=j+1;l<=n;l++){
    					int tmp=sum[k][l]-sum[i][l]-sum[k][j]+sum[i][j];
    					tt[tmp]--;
    				}
    			}
    		
    			for(int k=1;k<=i;k++){
    				for(int l=j+1;l<=n;l++){
    					int tmp=sum[i][l]-sum[i][j]-sum[k-1][l]+sum[k-1][j];
    					t[tmp]++;
    				}
    			}
    			for(int k=i+1;k<=n;k++){
    				for(int l=1;l<=j;l++){
    					int tmp=sum[k][j]-sum[k][l-1]-sum[i][j]+sum[i][l-1];
    					if(t[tmp]){
    						ans-=t[tmp]*tt[tmp];
    						tt[tmp]++;
    						ans+=t[tmp]*tt[tmp];
    					}
    				}
    			}
    		
    			for(int k=1;k<=i;k++){
    				for(int l=j+1;l<=n;l++){
    					int tmp=sum[i][l]-sum[i][j]-sum[k-1][l]+sum[k-1][j];
    					t[tmp]--;
    				}
    			}
    			for(int k=i+1;k<=n;k++){
    				for(int l=1;l<=j;l++){
    					int tmp=sum[k][j]-sum[k][l-1]-sum[i][j]+sum[i][l-1];
    					tt[tmp]--;
    				}
    			}
    		
    		}
    	}
    	printf("%lld\n",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    2978
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    55
    已通过
    13
    上传者