作者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