[ＡCM] 巴斯卡三角形的和

[x000032001 (某數..失業中)]

        ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
             ( 未必需要依照此格式，文章條理清楚即可 )

題號：
        http://zerojudge.tw/ShowProblem?problemid=d817

遇到的問題：
        想要做優化 讓程式跑得更快

有問題的code： (請善用置底文的標色功能)
        http://codepad.org/5hWl231W


補充說明：
        目前的成績是(212ms, 3972KB)
        測資經我不小心忘記處理EOF後得到共一萬筆
        但是加了input()作讀取優化似乎沒太大效用
        只差個幾十ms 另外的乘除取餘我都用了加減法做替代
        而unsigned long long int("%018llu")的版本反而比int還要慢
        想問問板友哪邊是可以再做加速的
        目前想到的就只有類似2^5000=2^2500*2^2500
        不過大數相乘應該會比較慢?
        另外VC++哪邊可以設定STACK SIZE呢 不然每次開新專案都要重新設定
        做大一點的DP或是大數就又要去設 冏>

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.137.151.115
※ 編輯: x000032001      來自: 114.137.151.115      (10/20 13:08)
推 loveme00835:傻眼...scanf不就有回傳直可以用? 管它是不是EOF
因為getchar這樣寫比scanf快 我本來也用scanf 大概差了幾十ms
推 purpose:printf、putchar少做幾次
※ 編輯: x000032001      來自: 114.137.215.139      (10/20 14:47)
→ bleed1979:我沒熱血回文了，寄給你程式碼。60ms，排名第一。
推 Severa:如果是運算加速  應該是數值方法的問題
→ x000032001:收到 完全不一樣的算法 甘拜下風XD
→ suhorng:2^n?
→ suhorng:這樣212ms喔(思)
推 prime2477:直接改值? 2^4:(binary)00000->10000
→ x000032001:那2^5000要怎麼改
→ wendly777:稍微研究一下你的程式碼，計算的部分花的時間大約花整
→ wendly777:體的1~3%左右而已，較花時間都是在input跟printf
→ wendly777:請改成用一個char[]去接，用itoa與strcat塞到字串，最
→ wendly777:後一次printf出去，速度就會快2~3倍吧
→ wendly777:這個例子告訴我們，最佳化要先研究哪部分花時間
→ x000032001:喔喔 我改成http://codepad.org/QYfQXh7o 變成了
→ x000032001:(128ms, 18.8MB) 快了6xms 不過input怎麼更快我不懂@@
→ x000032001:最後用malloc char[20萬] 結果是 (102ms, 10.8MB)
→ x000032001:比原本的快了一百多orz
→ wendly777:String雖然是動態長度，可是過程一定會反覆宣告記憶體
→ wendly777:宣告記憶體會拖慢一定速度