trang chủ / đề bài / icpc21_bt_e

Phân tích thành tổng

Đề bài

Mô tả

Cho số nguyên dương X và một tập P gồm các số nguyên dương. Hãy đếm số tổ hợp các phần tử của P có tổng bằng X. Mỗi phần tử của P có thể được dùng nhiều lần.

Dưới đây là ba ví dụ:

  • X=6, P={2,3,7}: có 2 tổ hợp là {2,2,2} và {3,3}.
  • X=7, P={2,7,3}: có 2 tổ hợp là {2,3,2} và {7}.
  • X=9, P={2,3,7,3}: có 3 tổ hợp là {2,7}, {2,2,2,3} và {3,3,3}.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương X.
  • Dòng thứ hai chứa N là số phần tử của P.
  • Dòng thứ ba chứa N số nguyên dương là các phần tử của P.

Dữ liệu ra

In ra số tổ hợp thỏa mãn. Nếu không có tổ hợp nào, in ra 0.

Ràng buộc

  • 1≤X≤106.
  • 2≤N≤9.
  • Mọi phần tử p của P thỏa mãn ⌊X/1000⌋+2≤p≤2·⌊X/1000⌋+7, trong đó ⌊X/1000⌋ là số nguyên lớn nhất không vượt quá X/1000.
  • Các phần tử của P có thể trùng nhau.
  • Số tổ hợp nhỏ hơn 1016.

Ví dụ

Input Output Giải thích
6
3
2 7 3
2 {2,2,2} và {3,3}.
7
3
2 7 3
2 {2,2,3} và {7}.
9
4
2 3 7 3
3 {2,7}, {2,2,2,3} và {3,3,3}; hai số 3 trong P không tạo ra tổ hợp mới.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0