HDU 6336.Problem E. Matrix from Arrays-子矩阵求和+规律+二维前缀和 (2018 Multi-University Training Contest 4 1005)

6336.Problem E. Matrix from Arrays

不想解释了，直接官方题解:

队友写了博客，我是水的他的代码

------>HDU 6336 子矩阵求和

至于为什么是4倍的，因为这个矩阵是左上半边有数，所以开4倍才能保证求的矩阵区域里面有数，就是图上的红色阴影部分，蓝色为待求解矩阵。

其他的就是容斥原理用一下，其他的就没什么了。

代码:

 //1005-6336-矩阵求和-二维前缀和+容斥-预处理O(1)查询输出

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<bitset>

 #include<cassert>

 #include<cctype>

 #include<cmath>

 #include<cstdlib>

 #include<ctime>

 #include<deque>

 #include<iomanip>

 #include<list>

 #include<map>

 #include<queue>

 #include<set>

 #include<stack>

 #include<vector>

 using namespace std;

 typedef long long ll;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const ll mod=1e9+;

 const int inf=0x3f3f3f3f;

 const int maxn=+;

 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

 ll n,a[maxn],sum[maxn][maxn];

 void init()

 {

     int cnt=;

     for(int i=;i<*n;++i){

         for(int j=;j<=i;++j){

             sum[j][i-j]=a[cnt];

             cnt=(cnt+)%n;

         }

     }

     for(int i=;i<*n;i++){

         for(int j=;j<*n;j++){

             if(i> &&j> ) sum[i][j]+=sum[i-][j]+sum[i][j-]-sum[i-][j-];

             if(i==&&j> ) sum[i][j]+=sum[i][j-];

             if(i> &&j==) sum[i][j]+=sum[i-][j];

         }

     }

 }

 ll GetAns(int x,int y)

 {

     ll ans=;

     ans+=(x/n)*(y/n)*sum[n-][n-];

     ans+=(y/n)*sum[x%n][n-];

     ans+=(x/n)*sum[n-][y%n];

     ans+=sum[x%n][y%n];

     return ans;

 }

 int main()

 {

     int t;scanf("%d",&t);

     while(t--){

         scanf("%lld",&n);

         for(int i=;i<n;i++)

             scanf("%lld",&a[i]);

         init();

         n=n*;

         int m;scanf("%d",&m);

         for(int i=;i<m;i++){

             int x1,y1,x2,y2;

             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

             ll ans=GetAns(x2,y2)-GetAns(x1-,y2)-GetAns(x2,y1-)+GetAns(x1-,y1-);//容斥

             printf("%lld\n",ans);

         }

     }

 }

溜了。

HDU 6336.Problem E. Matrix from Arrays-子矩阵求和+规律+二维前缀和 (2018 Multi-University Training Contest 4 1005)的相关教程结束。