互いに異なる値の硬貨が k 種類あり、種類ごとにいくらでも使える。
硬貨をいくつか選んで合計がちょうど N 円になる方法の数を 1,000,000,007 で割った余りを出力せよ。
種類ごとの使う枚数が同じなら同じ方法とする（順番は問わない：1+2 と 2+1 は一通り）。
硬貨を一枚も使わないのも方法なので、N = 0 なら答えは 1 である。
作れなければ 0 を出力する。
一行目に N と k、二行目に硬貨の値 c₁ … c_k が空白区切りで与えられる。
5 3 1 2 5
4
3 1 2
0
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ways[x] を「x 円を作る方法の数」とし、ways[0] = 1（何も使わない）から始めて、硬貨 c ごとに x = c … N で ways[x] += ways[x - c] をします。
k × N ≤ 100 万回なのでどの言語も速いです。
罠は二つ：ループの外側が硬貨、内側が金額でないと順番を問わない数になりません — 入れ替えると 1+2 と 2+1 を別々に数えます。
そして方法の数はすぐに 10¹⁸ をはるかに超えるので、足すたびに % 1000000007 をします。
最後に一度だけ割ると C・C++・Java・C# の long はあふれておかしな値になり、JavaScript・TypeScript・Craykon の数（倍精度）は 2^53 を超えたところで正確でなくなります。
Python だけは整数の大きさに限りがないので答えは合いますが、何百桁もの数を足すので遅くなります。
二つの値がどちらも 1,000,000,007 未満なら和は約 20 億で、32 ビット int（約 21 億）にぎりぎり収まります — なのでここでは int で足りますが、掛けたり三つ以上足したりするなら long/long long が必要です。
余りの演算はどこでも % です（Craykon も %）。
配列の作り方：Python [0] * (n + 1)、JS new Array(n + 1).fill(0)、C++ vector<int>(n + 1, 0)、Java・C# new int[n + 1]、C static int ways[10000]、Craykon 新リスト(n + 1, 0) — N は 9,999 までなので Craykon のリスト上限（10,000 個）に収まります。
MOD = 1_000_000_007 n, k = map(int, input().split())coins = list(map(int, input().split())) # ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다ways = [0] * (n + 1)ways[0] = 1for c in coins: for x in range(c, n + 1): ways[x] = (ways[x] + ways[x - c]) % MODprint(ways[n])const MOD = 1_000_000_007;const [n, k, ...coins] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다const ways = new Array(n + 1).fill(0);ways[0] = 1;for (const c of coins) { for (let x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD;}console.log(ways[n]);import { readFileSync } from "node:fs";const MOD = 1_000_000_007;const [n, k, ...coins]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다const ways: number[] = new Array(n + 1).fill(0);ways[0] = 1;for (const c of coins) { for (let x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD;}console.log(ways[n]);import java.util.Scanner; public class Main { static final int MOD = 1_000_000_007; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 int[] ways = new int[n + 1]; ways[0] = 1; for (int i = 0; i < k; i++) { int c = sc.nextInt(); // 두 값이 모두 MOD보다 작아서 합은 약 20억 — int(약 21억) 안에 든다 for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } System.out.println(ways[n]); }}using System;using System.Linq; class Program{ const int MOD = 1_000_000_007; static void Main() { int n = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[0]); int[] coins = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 int[] ways = new int[n + 1]; ways[0] = 1; foreach (int c in coins) { for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } Console.WriteLine(ways[n]); }}#include <iostream>#include <vector> constexpr int MOD = 1'000'000'007; int main() { int n, k; std::cin >> n >> k; // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 std::vector<int> ways(n + 1, 0); ways[0] = 1; for (int i = 0; i < k; i++) { int c; std::cin >> c; for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } std::cout << ways[n] << '\n';}#include <stdio.h> #define MOD 1000000007#define MAXN 9999 int main(void) { static int ways[MAXN + 1]; int n, k; scanf("%d %d", &n, &k); /* ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다 */ ways[0] = 1; for (int i = 0; i < k; i++) { int c; scanf("%d", &c); /* 두 값이 모두 MOD보다 작아서 합은 약 20억 — int(약 21억) 안에 든다 */ for (int x = c; x <= n; x++) ways[x] = (ways[x] + ways[x - c]) % MOD; } printf("%d\n", ways[n]); return 0;}MOD = 1000000007;첫줄 = コンソール.数読み();n = 첫줄[0];coins = コンソール.数読み(); // ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다ways = 新リスト(n + 1, 0);ways[0] = 1;それぞれ (c の中 coins){ 繰り返す (x = c; x <= n; x++) { ways[x] = (ways[x] + ways[x - c]) % MOD; }}コンソール.書く(ways[n]);