## 思路：

### Part $1$
我们可以想到枚举这个矩形的左上角和右上角，再用二位前缀和求出答案。但是如果枚举这个矩形的话，因为是枚举点，复杂度就是 $O(n^4)$。

我们看到这个 $n$ 和 $m$ 最大是 $400$，复杂度应该大概是 $O(n^3)$ 才对。

### Part $2$
我们应该考虑优化枚举。

枚举 $i$，代表枚举这个矩形的上边的行，枚举 $j$，表示这个矩形的下边的行，在枚举一个 $l$，表示这个矩形最右边的列。

我们可以用这个方式枚举出一个矩形。

![](https://cdn.luogu.com.cn/upload/image_hosting/sxp7jaq3.png)

我们枚举 $l$，也就是列的时候，设定当前的 $l$ 是 $l1$，设定这个枚举的矩阵和是 $x$，把这个 $x\bmod k$ 中的值，记在一个数组 $b$ 里面，记成一个桶。假设后面遍历到一个 $l$，管他叫 $l2$。$l2$ 这个矩形和模 $k$ 和 $l1$ 这个矩形和模 $k$ 结果一样。

![](https://cdn.luogu.com.cn/upload/image_hosting/bcvdlpv7.png)

那么用蓝色画的那部分矩形就是一个模 $k$ 等于 $0$ 的矩形，所以答案加上 $b_{x\%k}$ 的值。


可以写出代码：
```cpp
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m,k,a[510][510],pre[510][510],b[1000010],ans;
int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            memset(b,0,sizeof(b));
            for(int l=1;l<=m;l++){
                ll x=pre[j][l]-pre[i-1][l];
                if(x%k==0) ans++;
                ans=ans+b[x%k];
                b[x%k]++;
            }
        }
    }cout<<ans;
    return 0;
}
```

这时就能得到 $50$ 分的好成绩。
### Part $3$
我们可以看出是这个清空 $b$ 数组让我们错了，所以就要考虑优化。

我们发现这个数组不是每一个位置都会去改变，只会改变 $m$ 次，所以直接可以记录这个改变的地方，然后清空。

## 代码：
```cpp
//
// Created by 55062 on 2024/3/21.
//
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m,k,a[510][510],pre[510][510],ans,b[1000010],cnt[1000010],sum;
int main() {
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=1;k<=m;k++) b[cnt[k]]=0;
            for(int l=1;l<=m;l++){
                ll x=pre[j][l]-pre[i-1][l];
                if(x%k==0) ans++;
                ans=ans+b[x%k];
                cnt[l]=x%k;
                b[x%k]++;   
            }
        }
    }cout<<ans;
    return 0;
}
```