题解 P2332 【[SCOI2006]数字立方体】

· · 题解

练前缀和的一道好题。

首先可以考虑暴力做法。直接算前缀和就可以了（然而三维前缀和）。然而发现时间复杂度为O(n^6)不能过。于是可以考虑优化。

然后可以发现，如果一个立方体为所求的立方体的话，那么它的最高平面以下的方块数字和与它最低平面-1以下的方块数字和应该是相等的。所以可以考虑记录后快速加减。这样的话只需要枚举平面与高度就可以了。时间复杂度O(n^5)(其实也是勉强卡过去)

代码：

#include<bits/stdc++.h>
#include<cctype>
#include<algorithm>
#include<set>
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define Forward(i,a,b) for(i=(a);i>=(b);--i)
using namespace std;
template<typename T>//快读
inline void read(T &x)
{
    T s=0,f=1;
    char k=getchar();
    while(!isdigit(k)&&(k^'-'))k=getchar();
    if(!isdigit(k))
    {
        f=-1;
        k=getchar();
    }
    while(isdigit(k))
    {
        s=s*10+(k^48);
        k=getchar();
    }
    x=s*f;
}
const int MAXN=50;
int n,m;
long long sum[MAXN][MAXN][MAXN];//前缀和（long long可以不开）
int C[1000010],clean[100],e;//记录数组与清空数组。不这样清空的话时间复杂度为O(n^4m)根本过不了
int main(void)
{
    read(n);
    read(m);
    int i,j,k,x,y,z,ans=0;
    For(i,1,n)
        For(j,1,n)
            For(k,1,n)
            {
                read(sum[i][j][k]);
                sum[i][j][k]%=m;
                sum[i][j][k]=
                    (sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]+sum[i][j][k]

-sum[i-1][j-1][k]-sum[i][j-1][k-1]-sum[i-1][j][k-1] +sum[i-1][j-1][k-1]+3*m)%m;//计算前缀和

            }
    For(i,1,n)
        For(j,1,n)
            For(x,1,i)
                For(y,1,j)//枚举平面
                {
                    while(e)C[clean[e--]]=0;//清空之前平面的记录情况。
                    For(k,1,n)
                    {
                        int s=(sum[i][j][k]-sum[x-1][j][k]-sum[i][y-1][k]
                        +sum[x-1][y-1][k]+2*m)%m;//计算方块数字和
                        if(!C[s])clean[++e]=s;//计入清空数组
                        ans+=C[s];//加入答案
                        ++C[s];
                    }
                    ans+=C[0];//记得直接余0的需要再加上去
                }
    printf("%d\n",ans);
    return 0;
}