作者paae0226 (paae0226)
看板Prob_Solve
标题[问题] CF R152 Div.1 Problem E
时间Sat Apr 27 00:38:08 2013
题目连结:
http://ppt.cc/YglR
题意:
给 T 个查询，每个查訽是 (x1, y1), (x2, y2) 四个整数。
问在像下面这样的矩阵当中，(x1, y1), (x2, y2) 之间的子矩阵的元素和
-> +y
1 2 5 10 17 26
4 3 6 11 18 27
9 8 7 12 19 28
16 15 14 13 20 29
25 24 23 22 21 30
36 35 34 33 32 31
|
v
+x
如果答案超过 10 位数，则印 "..." 然後接上末 10 位数字，否则就直接印出该数字
T <= 10^5, 1 <= xi, yi <= 10^9
--------------------
因为我没有想到简单的方法判断数字是不是被 mod 过
所以直接刻了一个大数扔上去，结果当然是豪迈地 TLE 了
这题因为四则我都有用到，想请问一下如果不真正地算出精准的答案下
怎麽看最後的这个答案是不是被 mod 过的？
先谢谢各位
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.251.235.49
1F：推 LPH66:我的直觉你需要对你求出来的式子去做 mod 10^10 化简 04/27 02:33
2F：→ LPH66:不过因为还没能仔细算有些东西可能不那麽容易... 04/27 02:33
3F：→ LPH66:(例如你式子里的分母如果是偶数那就没这麽简单了) 04/27 02:33
4F：→ LPH66:啊我好像看懂你问题了...那就估计范围吧 04/27 02:34
5F：→ LPH66:估一下这个答案到底有没有超过 10^10 去判断 04/27 02:34
6F：推 seanwu:用double同步做一次，然後因为怕误差mod 10^11 04/27 03:04
7F：→ seanwu:这个是後来看到别人这样写，比赛的时候直接java大数了 04/27 03:12
8F：→ seanwu:所以大数应该ok，可能是你写版本的不够快XD 04/27 03:13
9F：→ paae0226:谢谢两位 我试试看 XD 04/27 13:10