[問題] 計算Pascal三角形前兩萬五千排分別mod1 …

看板Prob_Solve作者 (難得好天氣)時間14年前 (2011/03/26 21:47), 編輯推噓4(4推 0噓 12→)
留言16則, 7人參與, 最新討論串1/1
如題，http://www.cstutoringcenter.com上的題目。 大部分都蠻簡單的，不過有些想一陣子還不知道怎麼辦 本題就是把Pascal三角形中每個數都對100取餘數　並計算前兩萬五千排的總和 不知道mod 100後數列總和還有什麼關係？ 應該不是要算出這六千多萬個數再加起來吧ＸＤ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.103.233
→
03/26 22:59, , 1F
先把前幾排畫出來, 注意看看有什麼特性可以利用
03/26 22:59, 1F
推
03/26 23:00, , 2F
note the sume of each row
03/26 23:00, 2F
→
03/26 23:00, , 3F
type: sume -> sum
03/26 23:00, 3F
→
03/26 23:01, , 4F
未看先猜 Ans:51
03/26 23:01, 4F
推
03/26 23:10, , 5F
還沒想到什麼特別之處，不過把每一個算出來不到10秒就算完
03/26 23:10, 5F
→
03/26 23:10, , 6F
了，如果沒有時間限制的話硬算可能比較快
03/26 23:10, 6F
→
03/26 23:14, , 7F
1 2 1 = 4 1 3 3 1 = 8 1 4 6 4 1 = 16 ... ??
03/26 23:14, 7F
推
03/26 23:16, , 8F
最後結果有要 mod 100 嗎?
03/26 23:16, 8F
→
03/26 23:16, , 9F
這決定了是數學題還是程式題 XD
03/26 23:16, 9F
推
03/26 23:17, , 10F
應該是每一個數個自 mod 100 再加起來，所以是程式題 XD
03/26 23:17, 10F
→
03/26 23:18, , 11F
ex. ((40 % 7) + (60 % 7)) % 7 = 100 % 7
03/26 23:18, 11F
→
03/26 23:19, , 12F
這題最後不用再 mod 100 吧
03/26 23:19, 12F
→
03/26 23:21, , 13F
題目網址： http://ppt.cc/5yr;
03/26 23:21, 13F
→
03/26 23:40, , 14F
最後沒有要mod 100
03/26 23:40, 14F
如果最後還mod 100 的話 是還蠻trivial的...xDDD 題意應該是 一億多個 <100的數的總和 最後兩位數應該就是75沒錯 但是是每個數個別mod 最後總和沒有要在mod一次 看來答案應該是幾十億吧 所以真的要暴力加六千萬次XD? ※ 編輯: KitWoolsey 來自: 61.231.103.233 (03/26 23:44)
→
03/26 23:47, , 15F
一開始忘了放上原題連結讓各位誤會 抱歉@@
03/26 23:47, 15F
→
03/27 00:25, , 16F
窘 暴力我的Python跑了300秒...............
03/27 00:25, 16F
‣ 更多 KitWoolsey 的文章
文章代碼(AID): #1DZUvXXc (Prob_Solve)