#P2332. [SCOI2006] 数字立方体

[SCOI2006] 数字立方体

题目描述

有一个立方体被分成 n×n×nn\times n\times n 的单位,坐标用 (X,Y,Z)(X,Y,Z) 表示 (1X,Y,Zn)(1\le X,Y,Z\le n)。每个单位立方体内有一个绝对值不超过 10910^9 的整数。统计有多少个子立方体的所有数之和是 mm 的倍数。子立方体即满足 x1Xx2x_1\le X\le x_2y1Yy2y_1\le Y\le y_2z1Zz2z_1\le Z\le z_2 的所有单位立方体集合,其中 1x1,x2,y1,y2,z1,z2n1\le x_1,x_2,y_1,y_2,z_1,z_2\le n

输入格式

第一行有两个整数 n,mn, m,表示立方体的边长和作除数的正整数。

以下 n×nn\times n 行,每行有 nn 个整数。首先是 X=1,Y=1X=1, Y=1nn 个单位立方体,然后是 X=1,Y=2X=1, Y=2nn 个…最后是 X=n,Y=n1X=n, Y=n-1nn 个和 X=nX=nY=nY=nnn 个,共 n3n^3 个整数。

输出格式

输出仅包含一个数,即所有整数和为 mm 的倍数的子立方体的个数。

2 5
1 2
3 4
5 6
7 8

5

提示

数据范围及约定

  • 30%30\% 的数据满足 1n101\le n\le 10
  • 100%100\% 的数据满足 1n401\le n\le 40

对于所有的数据满足 1m1061\le m\le 10^6