有 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 ≤ 一百万次，各语言都很快。
两个陷阱：循环必须外层是硬币、内层是金额，才是不计顺序的数——交换后 1+2 和 2+1 会被分别计数。
另外方法数很快远超 10¹⁸，所以要每次相加时都 % 1000000007。
只在最后取一次余数，C、C++、Java、C# 的 long 会溢出成错误的值，JavaScript、TypeScript、Craykon 的数（双精度）超过 2^53 后就不再精确。
只有 Python 的整数没有大小上限，答案是对的，但要加几百位的数，会变慢。
两个值都小于 1,000,000,007 时和约为二十亿，刚好放得进 32 位 int（约二十一亿）——所以这里用 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]);