如果想計算一個很大的數字的話，可以試試這個網站: 階乘計算機

它應該可以幫你 debug

這題適用 dp 的原因是計算階乘時，我們不希望讓程式重新算已經算過的東西，而階乘就完全符合條件

階乘的公式: n! = n * (n-1)!

每一項的結果都和前一項有關

不用 dp 的話...應該會算到天荒地老

但這依然有些許問題，20! 的數字大小就已經超過 long long 的範圍了，而這題最大可能是 100000! ，有 35660 位數，還沒動手就可以預見 MLE 了，硬算顯然不理智，所以我們要取模，取多少呢?

數字取大了，算的速度就慢，也有 MLE 的風險，數字小了又會丟失精度

先說答案: 這題應該取 100000，保留五位數字

在這題中，我們只關注從右邊數過來第一個不是 0 的數字

你可以跑一個 while 循環一直將數字除以 10 取整數，直到 mod 10 不為 0 為止，這樣就可以讓數字右側沒有 0

python 也可以把得到的數字轉成 str 後 rstrip('0') ，再轉回 int

這樣就可以忽略 0 的部分了

對於 n! 的結果，題目提到 n 最大為 100000，所以我們就只需要將每個結果 mod 10000 就可以了，這樣就可以在避免大數運算的同時，保持最後五位數數字的精度

狀態轉移公式: dp[n] = (n * dp[n-1] ->去掉右側多餘的0 ) % 100000

最後只需要查表即可

參考答案: gist(python)