Số không may mắn

Điểm: 1,54 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

Thầy Ðỗ Ðức Ðông

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một số nguyên dương được gọi là may mắn nếu tổng một số chữ số bằng tổng của các chữ số còn lại, ví dụ: ~561743~ sẽ là số may mắn vì ~5 + 1 + 4 + 3 = 6 + 7~. Tuy nhiên số may mắn không nhiều, nên người ta muốn đếm xem có bao nhiêu số không may mắn.

Yêu cầu: Tính số lượng số không may mắn có ~n~ chữ số và chỉ chứa các chữ số trong phạm vi từ ~0~ đến ~k~. Các số có thể bắt đầu bằng các số ~0~.

Input

Gồm nhiều dòng, mỗi dòng chứa ~2~ số ~n~ và ~k~ ~(1 \leq n \leq 20~, ~1 \leq k \leq 9~, có không quá ~5~ dòng).

Output

Gồm nhiều dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Sample Input

1 5
4 3

Sample Output

5
164

Bình luận

Hãy đọc nội quy trước khi bình luận.

2
KAKOII đã bình luận lúc 30, Tháng 6, 2025, 12:09 ← sửa 3 →
Ta giải quyết bài toán này bằng QHĐ chữ số:

Ta có ~(idx, sum, possibleSum)~ lần lượt là các trạng thái: số thứ ~idx~ đang xét, tổng các chữ số trước và danh sách các tổng có thể hình thành từ những chữ số đã được điền.

Khi ta điền số ~i~ (~0 \le i \le k~) vào vị trí ~idx~, việc chuyển trạng thái từ ~(idx, sum, possibleSum)~ sang ~(idx^*, sum^*, possibleSum^*)~ diễn ra như sau:

~idx^*= idx - 1~

~sum^* = sum + i~

~possibleSum^* = possibleSum \cup \{x \in possibleSum \space | \space x + i\}~

Khi ~idx < 0~:

Nếu ~sum~ lẻ thì số đó là một số không may mắn

Nếu ~sum~ chẵn thì số đó là một số không may mắn khi ~sum > 0~ và ~\frac{sum}{2} \notin possibleSum~

Số lượng số không may mẵn có ~n~ chữ số và chỉ chứa các chữ số trong phạm vi từ ~0~ đến ~k~ bằng ~f(n - 1, 0, \{0\})~.

Code hàm QHĐ chữ số hoạt động như sau:

map<tuple<int, int, vector<bool>>, __int128> memo; __int128 f(int idx, int sum, vector<bool> &possum){ if(idx < 0){ if(sum & 1) return 1; return (sum > 0) && !possum[sum >> 1]; } tuple<int, int, vector<bool>> state = make_tuple(idx, sum, possum); if(memo.find(state) != memo.end()) return memo[state]; __int128 ans = 0; for(int digit = 0; digit <= k; ++digit){ vector<bool> newpossum = possum; for(int j = sum; j >= 0; --j){ if(possum[j]) newpossum[digit + j] = 1; } ans += f(idx - 1, sum + digit, newpossum); } return memo[state] = ans; }

Sử dụng code QHĐ chữ số trên có thể sinh hết tất cả các cặp test ~(n, k)~ trong chưa đầy một phút.