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