【题意】数组矩阵

题意

给你一个长度为的数组，由构造出一个的矩阵，其中，问中有多少个子矩阵的和为。

题解

考虑这个子矩阵的和为什么有： 。
若我们预处理出数组的前缀和那么上式就可以表示为：
由于的大小为，我们可以统计出所有的区间和的个数。然后再跑一遍每个区间的和，那么答案就是加上当前枚举的和的个数和的个数。
当时还需特判一下。若，那么会使得的第行和第列的取值都是，一行会产生个满足条件的子矩阵，而第行和第列同时为的话，就会产生个子矩阵，不过需要注意一下，这个格子被计算了两次，所以需要减去。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long cnt[N];
int sum[N];
int a[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<=n; i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            cnt[sum[i]-sum[j-1]]++;
    if(k==0)
    {
        printf("%lld\n",cnt[0]*n*(n+1)-cnt[0]*cnt[0]);
        return 0;
    }
    long long ans=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
        {
            int num=sum[i]-sum[j-1];
            if(num!=0&&k%num==0&&k/num<N)
                ans+=cnt[k/num];
        }
    printf("%lld\n",ans);
    return 0;
}