There are k kinds of coins with distinct values, and each kind can be used any number of times. Print the number of ways to choose coins whose total is exactly N, modulo 1,000,000,007. Two ways are the same if they use the same number of coins of each kind (order does not matter: 1+2 and 2+1 are one way). Using no coins at all is also a way, so for N = 0 the answer is 1. If N cannot be made, print 0.
The first line gives N and k, and the second line gives the coin values c₁ … c_k separated by spaces.
Input
0 ≤ N ≤ 9,999, 1 ≤ k ≤ 100, 1 ≤ cᵢ ≤ 10,000, all cᵢ distinct
Output
The number of ways modulo 1,000,000,007 (one integer)
Example 1 · stdin
5 3
1 2 5
stdout
4
Example 2 · stdin
3 1
2
stdout
0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Let ways[x] be 'the number of ways to make x', start from ways[0] = 1 (use nothing), and for each coin c do ways[x] += ways[x - c] for x = c … N. That is k × N ≤ 1 million steps, fast in every language. Two traps: the outer loop must be over coins and the inner over amounts to count without order — swap them and 1+2 and 2+1 are counted separately. And the count quickly passes 10¹⁸, so apply % 1000000007on every addition. Taking the remainder only at the end overflows long in C, C++, Java and C# into garbage, and JavaScript, TypeScript and Craykon numbers (doubles) stop being exact past 2^53. Only Python has unbounded integers, so its answer is right, but adding numbers hundreds of digits long makes it slow. When both values are below 1,000,000,007 their sum is about 2 billion, which just fits a 32-bit int (about 2.1 billion) — so int is enough here, but multiplying or adding three or more needs long/long long. The remainder operator is % everywhere (Craykon too). Making the array: 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 NewList(n + 1, 0) — N goes up to 9,999, which fits Craykon's list limit of 10,000 items.
Pythonmain.py · 12 lines
MOD = 1_000_000_007n, 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])
JavaScriptmain.js · 10 lines
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]);
TypeScriptmain.ts · 11 lines
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]);
JavaMain.java · 19 lines
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]); }}
C#Main.cs · 22 lines
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]); }}
C++main.cpp · 18 lines
#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';}
Cmain.c · 20 lines
#include <stdio.h>#define MOD 1000000007#define MAXN 9999int 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;}
Craykonmain.cray · 16 lines
MOD = 1000000007;첫줄 = Console.ReadNumbers();n = 첫줄[0];coins = Console.ReadNumbers();// ways[x] = x원을 만드는 방법 수. 동전 종류를 바깥에 두면 순서만 다른 것을 한 번만 센다ways = NewList(n + 1, 0);ways[0] = 1;foreach (c in coins){ for (x = c; x <= n; x++) { ways[x] = (ways[x] + ways[x - c]) % MOD; }}Console.WriteLine(ways[n]);