矩阵价值和

这里写图片描述

60分的做法：O(n^2) 处理出矩阵的前缀和，那么就可以O(1)地查询任意矩阵的大小，O(n^4)枚举所有矩阵，求出答案。

100分的做法：
这里写图片描述

对于1号点和2号点，它们两个结合是对答案的贡献是：

2 * a [i 1] [j 1] * a [i 2] [j 2] - - - ①

+

a [i 1] [j 1] 2 + a [i 2] [j 2] 2 - - - ②

那么它们结合的次数同时包含它们两个的矩阵的个数=L1*L2*L3*L4（很显然，两个小矩阵）
那么以①式的形式它们对答案的贡献是

2 * a [i 1] [j 1] * a [i 2] [j 2] * L 1 * L 2 * L 3 * L 4 (i 2 > i 1 而 且 j 2 > j 1) - - - ③

如果我们枚举i1，i2，j1，j2，时间复杂度还是O(n^4)，还是不行。
那么我们枚举i2和j2，对于这一个点，i1,j1就是她左上方的所有点，
我们令C=2*a[i2][j2]*L3*L4，那么③式就等于C*a[i1][j1]*i1*j2，我们可以对a[i][j]*i*j在O(n^2)做一个前缀和。那我们就可以O(n^2)求出以（i2,j2）为右下角的所有矩形对答案的贡献。

对于右上角，同理，有变化的是L1,L2,L3,L4与i，j的关系（即表示方法），还有前缀和是a[i][j]i(n-j+1)，因为右上方小矩形两条边长为 i 和 n-j+1。
注意一些细节，在代码的注释中。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MOD 1000000007
#define LL long long
#define PP(x) (x)*(x)
using namespace std;
int N;
LL a[3001][3001],s[3001][3001],b[3001][3001];
LL get_ans(LL n,LL i,LL j)
{
  LL x=min(i-1,n-i);
  x=min(x,j-1);
  x=min(x,n-j);
  LL ans=(4*n*x-4*x*x)%MOD;

  if(i-x==1)ans=(ans+j-x)%MOD;
  else 
   if(i+x==n)ans=(ans+3*n-5*x-1-j)%MOD;
    else 
     if(j-x==1)ans=(ans+4*n-7*x-2-i)%MOD;
      else ans=(ans+n-3*x+i-1)%MOD;
   return ans;
} 
void pre(int n)
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++){
        a[i][j]=get_ans(n,i,j);
     }
}
int main() 
{
    scanf("%d",&N); 
    pre(N);

    LL ans=0;  
    for(int i=1;i<=N;i++)//左上角 
     for(int j=1;j<=N;j++)
     {
         b[i][j]=a[i][j]*i%MOD*j%MOD;
         s[i][j]=(s[i-1][j]+s[i][j-1]-s[i-1][j-1]+b[i][j]+MOD)%MOD;//左上角a(i,j)*i*j前缀和 

         ans=(ans-(a[i][j]*i*j%MOD*a[i][j])%MOD*(1ll*(N-i+1)*1ll*(N-j+1))%MOD+MOD)%MOD;//本身的平方系数为2*……的一半，所以去掉一倍
         ans=(ans+2*a[i][j]*s[i][j]%MOD*(1ll*(N-i+1)*1ll*(N-j+1))%MOD+MOD)%MOD;
     }

    for(int i=1;i<=N;i++)//右上角 
     for(int j=N;j>=1;j--)
     {
         b[i][j]=a[i][j]*i%MOD*(N-j+1)%MOD;
         s[i][j]=(s[i-1][j]+s[i][j+1]-s[i-1][j+1]+b[i][j]+MOD)%MOD;//右上角a(i,j)*i*(n-j+1)前缀和 
         ans=(ans+2*a[i][j]*s[i-1][j+1]%MOD*(1ll*(N-i+1)*1ll*j)%MOD+MOD)%MOD;//*s[i-1][j+1]防止i,j所在行列的重复 
     }

    printf("%lld
",ans);
    return 0;
}