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