在这里%一波$mathscr{ZMY}$搭题目。
题意：
给定$n imes n$的矩阵$A$,$B$，$m$次询问，求$C=A imes B$的子矩阵和。
$1le nle 800,; 1le mle 10^4,; 0le A_{i,j}le 100$
分析：
设询问子矩阵为$[i_1:i_2][j_1:j_2]$，则
$quadsumlimits_{i=i_1}^{i_2}sumlimits_{j=j_1}^{j_2}sumlimits_{k=1}^{n}A[i][k] imes B[k][j]$
$=sumlimits_{k=1}^{n}sumlimits_{i=i_1}^{i_2}A[i][k]sumlimits_{j=j_1}^{j_2}B[k][j]$
$=sumlimits_{k=1}^{n}A[i_1:i_2][k] imes B[k][j_1:j_2]$
于是$O(n^2)$预处理$A$每列的前缀和，$B$每行的前缀和，$O(n)$询问。
实现（100分）：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #define IL inline #define UI unsigned int #define RI register int using namespace std; typedef long long LL; const int N=800; IL void read(int &x){ char ch; while(!isdigit(ch=getchar())); x=ch-'0'; while(isdigit(ch=getchar())) x=(x<<3)+(x<<1)+ch-'0'; } IL void read(int &x,int &y){ read(x); read(y); } IL void read(int &x,int &y,int &p,int &q){ read(x); read(y); read(p); read(q); } IL void read(LL &x){ char ch; while(!isdigit(ch=getchar())); x=ch-'0'; while(isdigit(ch=getchar())) x=(x<<3LL)+(x<<1LL)+ch-'0'; } int n,m; LL a[N+3][N+3],b[N+3][N+3]; LL s1[N+3][N+3],s2[N+3][N+3]; IL LL sum1(int i1,int i2,int k){ return s1[i2][k]-s1[i1-1][k]; } IL LL sum2(int k,int j1,int j2){ return s2[k][j2]-s2[k][j1-1]; } int main(){ read(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(b[i][j]); memset(s1,0,sizeof s1); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) s1[i][k]=s1[i-1][k]+a[i][k]; memset(s2,0,sizeof s2); for(int k=1;k<=n;k++) for(int j=1;j<=n;j++) s2[k][j]=s2[k][j-1]+b[k][j]; while(m--){ int p1,p2,p3,p4; read(p1,p2,p3,p4); if(p1>p3)swap(p1,p3); if(p2>p4)swap(p2,p4); LL ans=0; for(int k=1;k<=n;k++) ans+=sum1(p1,p3,k)*sum2(k,p2,p4); printf("%lld ",ans); } return 0; }
小结：
快速推式子上手。