MojoでProject Euler 31（1）

https://projecteuler.net/problem=31

合計Nに対して、使える硬貨をN以下で最上位桁が1, 2, 5となるものすべてと問題拡張しています。また、すぐに結果が大きくなるので、適当な数の剰余を答えにしています。
1pだけ使ったとき各金額で何通りあるか、2pを追加したら何通りあるか、というように計算していけばよいです。計算量はです。

import sys


#################### constatns ####################

var D = 10**9+7


#################### process ####################

fn collect_coins(N: Int) -> List[Int]:
    var ns = List[Int](1, 2, 5);
    var ps = List[Int]()
    for e in range(19):
        for n in ns:
            var p = n[] * 10**e
            if p > N:
                break
            ps.append(p)
    return ps

fn initialize_dp(N: Int) -> List[Int]:
    var dp = List[Int]()
    dp.append(1)
    for _ in range(1, N+1):
        dp.append(0)
    return dp

fn update_dp(a: Int, dp: List[Int]) -> List[Int]:
    var N = dp.size
    var new_dp = List[Int]()
    for _ in range(N+1):
        new_dp.append(0)
    for i in range(N+1):
        if dp[i] == 0:
            continue
        for n in range((N - i)//a+1):
            new_dp[i+a*n] = (new_dp[i+a*n] + dp[i]) % D
    return new_dp

fn f(N: Int) -> Int:
    var dp = initialize_dp(N)
    var ps = collect_coins(N)
    for p in ps:
        dp = update_dp(p[], dp)
    return dp[N]

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))