核心内容摘要
www.免费：解锁无限可能，开启你的精彩生活！
P3941 入阵曲题目背景pdf题面和大样例链接http://pan.baidu.com/s/1cawM7c 密码xgxv丹青千秋酿一醉解愁肠。
无悔少年枉只愿壮志狂。
题目描述小 F 很喜欢数学但是到了高中以后数学总是考不好。
有一天他在数学课上发起了呆他想起了过去的一年。
一年前当他初识算法竞赛的时候觉得整个世界都焕然一新。
这世界上怎么会有这么多奇妙的东西曾经自己觉得难以解决的问题被一个又一个算法轻松解决。
小 F 当时暗自觉得与自己的幼稚相比起来还有好多要学习的呢。
一年过去了想想都还有点恍惚。
他至今还能记得某天晚上听着入阵曲激动地睡不着觉写题写到鸡鸣时分都兴奋不已。
也许这就是热血吧。
也就是在那个时候小 F 学会了矩阵乘法。
让两个矩阵乘几次就能算出斐波那契数列的第1010010^{100}10100项真是奇妙无比呢。
不过小 F 现在可不想手算矩阵乘法——他觉得好麻烦。
取而代之的是一个简单的小问题。
他写写画画画出了一个n×mn \times mn×m的矩阵每个格子里都有一个不超过kkk的正整数。
小 F 想问问你这个矩阵里有多少个不同的子矩形中的数字之和是kkk的倍数 如果把一个子矩形用它的左上角和右下角描述为(x1,y1,x2,y
(x_1,y_1,x_2,y_
(x1,y1,x2,y2)其中x1≤x2,y1≤y2x_1 \le x_2,y_1 \le y_2x1≤x2,y1≤y2 那么我们认为两个子矩形是不同的当且仅当他们以(x1,y1,x2,y
(x_1,y_1,x_2,y_
(x1,y1,x2,y2)表示时不同也就是说只要两个矩形以(x1,y1,x2,y
(x_1,y_1,x_2,y_
(x1,y1,x2,y2)表示时相同就认为这两个矩形是同一个矩形你应该在你的答案里只算一次。
输入格式从标准输入中读入数据。
输入第一行包含三个正整数n,m,kn,m,kn,m,k。
输入接下来nnn行每行包含mmm个正整数第iii行第jjj列表示矩阵中第iii行第jjj列 中所填的正整数ai,ja_{i,j}ai,j。
输出格式输出到标准输出中。
输入一行一个非负整数表示你的答案。
输入输出样例 #1输入 #12 3 2 1 2 1 2 1 2输出 #16说明/提示【样例 1 说明】这些矩形是符合要求的(1,1,1,
,(1,1,2,
,(1,2,1,
,(1,2,2,
,(2,1,2,
,(2,3,2,
(1, 1, 1,
,(1, 1, 2,
,(1, 2, 1,
,(1, 2, 2,
,(2, 1, 2,
,(2, 3, 2,
(1,1,1,
,(1,1,2,
,(1,2,1,
,(1,2,2,
,(2,1,2,
,(2,3,2,
。
子任务会给出部分测试数据的特点。
如果你在解决题目中遇到了困难可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表特殊性质保证所有ai,ja_{i,j}ai,j均相同。
C实现#includebits/stdc.husingnamespacestd;typedeflonglongLL;#defineN405intn,m,K;inta[N][N],b[N],cnt[1000005];LL ans0;intmain(){scanf(%d%d%d,n,m,K);for(inti1;in;i)for(intj1;jm;j){scanf(%d,a[i]j);(a[i][j]a[i-1][j]a[i][j-1]K-a[i-1][j-1])%K;}for(inti0;in;i){for(intji1;jn;j){cnt[0]1;for(intk1;km;k)anscnt[(b[k]a[j][k]K-a[i][k])%K];for(intk1;km;k)cnt[b[k]]0;}}printf(%lld\n,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容