解题思路

暴力做法：$O(n^6)$枚举子立方体

考虑只枚举长和宽，为了简化问题，我们可以将问题表示成：

给定一个矩阵，求有多少个子矩阵的和为$M$的倍数

我们可以不必枚举宽，仅仅用$O(n^2)$枚举长，然后对于给定的行数，维护一个前缀和$s[i]$。于是一个子矩阵的和就可以表示为$s[r]-s[l-1]$。考虑一下何时这个子矩阵是$M$的倍数？用同余方程描述，就是$$s[r]-s[l-1]≡0 \ (mod \ M)$$也就是$$s[l-1]≡s[r] \ (mod \ M)$$于是我们只需要维护一个桶表示目前为止$s[r]==i$的个数就可以了

推广到立方体，改一下前缀和的计算公式就可以了

$s[i][j][k] = s[i-1][j][k] + s[i][j-1][k] - s[i-1][j-1][k] + s[i][j][k-1] - s[i-1][j][k-1] - s[i][j-1][k-1] + s[i-1][j-1][k-1] + a[i][j][k]$

反思

注意这道题问的是$M$的倍数，有关和，而且涉及倍数——一个前缀和，一个数论，就都可以解决了。

Code

注意循环变量的初始值。由于如果每次把桶清零非常耗时，一个优化是只清当前这轮涉及到的。当前这轮最多涉及到$N$个，因此非常快。

/*By DennyQi 2018*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 10010;

const int MAXM = 20010;

const int INF = 1061109567;

inline int Max(const int a, const int b){ return (a > b) ? a : b; }

inline int Min(const int a, const int b){ return (a < b) ? a : b; }

inline int read(){

    int x = 0; int w = 1; register char c = getchar();

    for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());

    if(c == '-') w = -1, c = getchar();

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;

}

ll Ans;

int N,M,K;

int a[45][45][45],s[45][45][45],sum[45],cnt[1000010];

int main(){

//	freopen(".in","r",stdin);

	N = read(), M = read();

	for(int i = 1; i <= N; ++i){

		for(int j = 1; j <= N; ++j){

			for(int k = 1; k <= N; ++k){

				a[i][j][k] = read();

				s[i][j][k] = ((s[i-1][j][k] + s[i][j-1][k] - s[i-1][j-1][k] + s[i][j][k-1] - s[i-1][j][k-1] - s[i][j-1][k-1] + s[i-1][j-1][k-1] + a[i][j][k]) % M + M) % M;

			}

		}

	}

	for(int i = 1; i <= N; ++i){

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

			for(int p = 1; p <= N; ++p){

				for(int q = p; q <= N; ++q){

					cnt[0] = 1;

					for(int k = 1; k <= N; ++k){

						sum[k] = ((s[j][q][k]-s[i-1][q][k]-s[j][p-1][k]+s[i-1][p-1][k]) % M + M) % M;

						Ans += 1ll * cnt[sum[k]];

						cnt[sum[k]]++;

					}

					for(int k = 1; k <= N; ++k) cnt[sum[k]] = 0;

				}

			}

		}

	}

	printf("%lld", Ans);

	return 0;

}

巴特西

[SCOI2006] 数字立方体

解题思路

反思

Code

最新文章

热门文章