algorithm - 幸运票(计算幸运数字的数量，具有指定的所有数字总和)

Question

这是 problem

You are given a number 1 ≤ N ≤ 50. Every ticket has its 2N-digit number. We call a ticket lucky, if the sum of its first N digits is equal to the sum of its last N digits. You are also given the sum of ALL digits in the number. Your task is to count an amount of lucky numbers, having the specified sum of ALL digits.

对于输入 2 2 输出为 4 (0101, 0110, 1001, 1010)

你能帮我解决这个问题吗？最低复杂度是多少？

Answer 1

如果要求的总和是s，那么每一半的总和必须是s/2。现在，您需要求 f(n, s/2):有多少个 n 位数字的和为 s/2。知道f(n, s/2)，一行就可以得出答案(自己试试看吧)。

至于如何计算f(n, m):那是标准的DP。你有像 f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + 这样的递归公式f(n-1, m-9)。这里，0, 1, 2, .. 9 是给定数字最后一位的所有可能选项。如果最后一个数字是 k，那么剩下的是 (n-1) - 长数字，数字总和为 m - k。

希望对您有所帮助。

PS 根据问题的限制，你需要一些长算术来通过它。