丹青千秋酿，一醉解愁肠。
无悔少年枉，只愿壮志狂。
这种结构本来在博客里面写到过。
就是多对多。
但是认为这是数据结构或者快速幂之类的作用。
但是放在最普通而简单的数组存储也可以发挥很大作用。
（桶，桶的作用）每次一个个查->一次查完，一起共享。
桶虽然只是数组，但是它的思想可以做一个专题。
多对多在于之前已经存在过的。
暴力枚举再判断，统计正确的个数，不如直接设法询问有多少个是正确的。
还是观察矩阵找一下性质就能发现了。
T1是应该A掉的。
这两次T1都是贪心。
最重要的还是找规律。
去观察，去发现。
如何运用还是不熟悉。
维护一个桶。数据存储与查询是为了去掉很多无效的枚举。
观察发现询问K的倍数，很特殊。这是一个突破点。
大概应该顺着的思路or复盘:
n^4暴力想出来以后，去想优化。
1、正解可能n^3就够了，或者n^3log,n^2log^2
2、但是第一题一般是找规律，不会出一些傻逼数据结构，不太可能用log
3、再考虑倍增，无法处理内部细分（倍增是跳过中间过程，而这题需要中间过程）;
考虑分治。尝试建立横纵轴，分成四块。发现太难实现，细节太多。而且T1要不然不会这么难，要不然神题不可做（结合以往考试难度经验）
（真是高级算法学傻了）
3.5:另：发现K的倍数很特殊，考虑优化。但是只想到前缀和数组可以取模，不用开long long.
4、分流点：考试时此处开始偏离正确轨道
考试时:想了想能否n^3之类，
观察矩阵的计算，四个小矩阵组合成一个打矩阵，很难优化。
试图拼接，把两个%K后相加等于K的拼起来。发现不会实现。
没思路，弃了，准备回头打。
正确模式：
看测试点n^2太小，n^4又太大，不是n^3就是带log.
很大概率是n^3.因为是奇数，无法枚举全两个维度。
ans 是 long long级别，直接++肯定不行。应该是ans+=x. +=，联想到桶。数组里存储并查询数据。
于是考虑一个长条（或一个横条）。
在一个长条里，l 和r 固定，变化的是up和down.
考虑矩阵的前缀和计算。这里只要用大矩阵减去小矩阵即可。
考虑特殊要求：K的倍数。
当大小矩阵模K值相同时，
相减得到的新矩阵是K的倍数。（一大减一小，取模相同相差整数倍）。
那么我们就可以在l 和 r 确定时，用桶存储权值出现次数，o(n)求出一个长条了。
思想是 暴力枚举再判断，统计正确的个数，不如直接设法询问有多少个是正确的。
那么枚举l和r是n^2的，总复杂度O(n^3)。
于是我们就愉快的切了这道题。
另：题解思路：
尝试先想一维序列上的做法。
前缀和以后是n^2枚举O(1)计算。
优化？能否不枚举？
->取模后值相同，O(n)扫一遍。
->扩展到2维。
部分矩阵的题可以先降维，然后推导过来。，每列只有一个数值则可以直接转化为序列上的题。
相当与放弃了暴力做法里面的矩阵的一般容斥方式。所以在无法拓展下去时要尝试跳出已有的方式。
考试时想拼接，正解是剪切。所以正难则反。平时也是考虑相加多过相减。要多考虑相减。
由于直接去想复杂做法，而没有考虑一些简单的性质，与正解失之交臂。
那么这题还是可以并且应该A掉的，只不过处于全局考虑打出暴力后去做了T2T3。是对的。对于以后更进一步就是思考快点，固定思考时间（平时也是）。从而有时间来
拿到可以拿到的东西。还是总体速度慢了。应该尽力提速。
#include<bits/stdc++.h> #define F(i,a,b) for(rg int i=a;i<=b;++i) #define il inline #define rg register #define pf(a) printf("%d ",a) #define phn puts("") #define LL long long using namespace std; int read(); /* 这种结构本来在博客里面写到过。 就是多对多。 认为这是数据结构或者快速幂之类的作用。 但是放在最普通而简单的数组存储也可以发挥很大作用。 （桶，桶的作用） 桶虽然只是数组，但是它的思想可以做一个专题。 多对多在于之前已经存在过的。 暴力枚举再判断，统计正确的个数，不如直接设法询问有多少个是正确的。 还是观察矩阵找一下性质就能发现了。 T1是应该A掉的。 这两次T1都是贪心。 最重要的还是找规律。 去观察，去发现。 如何运用还是不熟悉。 维护一个桶。 观察发现询问K的倍数，很特殊。这是一个突破点。 */ int n,m,K; int a[405][405];int s[405][405]; int t[1001110]; int main(){ n=read();m=read();K=read(); rg LL ans=0; F(i,1,n){ F(j,1,m){ a[i][j]=read();s[i][j]=(s[i][j-1]+a[i][j])%K; } } F(i,1,n){ F(j,1,m){ (s[i][j]+=s[i-1][j])%=K; } } t[0]=1; F(l,1,m){ F(r,l,m){ F(i,1,n){ ans+=t[(s[i][r]-s[i][l-1]+K)%K]; ++t[(s[i][r]-s[i][l-1]+K)%K]; } F(i,1,n){ --t[(s[i][r]-s[i][l-1]+K)%K]; } } } printf("%lld ",ans); } il int read(){ int s=0;char ch; while(ch=getchar(),!isdigit(ch)); for(;isdigit(ch);s=s*10+(ch^48),ch=getchar()); return s; } /* g++ 1.cpp -g
#include<bits/stdc++.h> #define F(i,a,b) for(rg int i=a;i<=b;++i) #define il inline #define rg register #define pf(a) printf("%d ",a) #define phn puts("") #define LL long long using namespace std; int read(); /* 这种结构本来在博客里面写到过。 就是多对多。 认为这是数据结构或者快速幂之类的作用。 但是放在最普通而简单的数组存储也可以发挥很大作用。 （桶，桶的作用） 桶虽然只是数组，但是它的思想可以做一个专题。 多对多在于之前已经存在过的。 暴力枚举再判断，统计正确的个数，不如直接设法询问有多少个是正确的。 还是观察矩阵找一下性质就能发现了。 T1是应该A掉的。 这两次T1都是贪心。 最重要的还是找规律。 去观察，去发现。 如何运用还是不熟悉。 维护一个桶。 观察发现询问K的倍数，很特殊。这是一个突破点。 */ int n,m,K; int a[405][405];int s[405][405]; int t[1001110]; int main(){ n=read();m=read();K=read(); rg LL ans=0; F(i,1,n){ F(j,1,m){ a[i][j]=read();s[i][j]=(s[i][j-1]+a[i][j])%K; } } F(i,1,n){ F(j,1,m){ (s[i][j]+=s[i-1][j])%=K; } } t[0]=1;//这里要加一，因为如果他自己就是K的倍数，相当于减一个大小为0的矩阵。 F(l,1,m){ F(r,l,m){ F(i,1,n){ ans+=t[(s[i][r]-s[i][l-1]+K)%K]; ++t[(s[i][r]-s[i][l-1]+K)%K]; } F(i,1,n){ --t[(s[i][r]-s[i][l-1]+K)%K]; } } } printf("%lld ",ans); } il int read(){ int s=0;char ch; while(ch=getchar(),!isdigit(ch)); for(;isdigit(ch);s=s*10+(ch^48),ch=getchar()); return s; } /* g++ 1.cpp -g ./a.out 2 3 2 1 2 1 2 1 2 */ //asd123mzz
考察点：观察性质、转化问题、for循环写法（乌）、前缀和数组求法（雾）、取模不必开long long（吴）。
我们不能忘记伟大的Paris的教诲：寻找冗余。
伟大的达拉崩吧斑得贝迪卜多比鲁翁
Da La Beng Bar spotted Bedi Budo Biroun
———自信来源于自律。