Problem Description
The integer n is divided into K, and each copy cannot be empty, any two kinds of degradation cannot be the same (regardless of the order). For example: n = 7, k = 3, the following three categories are considered to be the same: 1, 1, 5; 1, 5, 1; 5, 1, 1. Ask how many different ci devices. Enter: n, k (6 Input and output sample Enter: 7 3 Output: 4 problem analysis: This is a problem of integer. This type of problem is very mathematically, and there are many methods. First, the correct understanding "Integer n is divided into K, this k integer does not consider the order of the order" means that the same division is independent of the alignment of K integers, such as the 4 division of the following is as the same division method. : 1 2 2 3; 2 2 3 1; 1 3 2 2; 3 2 1 2; 2 2 1 3. Therefore, a method of dividing the n-division is N1 N2 ... NK, wherein N1 <= n2 <= .... Nk. This can be regarded as the K column of N as the K columns in the N-blocks, and the number of blocks per column is incremented, that is, the N-blocks are piled up from left to right into "stepped". . For example, the following figure is several division of division of 10: Rotate the three rectangles of the above clockwise 90 degrees, as shown below: It is not difficult to find that the model after the selection is divided into 10, but the constraint conditions are different. Obviously, because it is k, the biggest one in the new model is inevitably k. The rest of the elements are not limited, but they can not be greater than k. N to minus K, N '= NK, the remaining problem is to ask any part of N', and each element is not more than k. The total number of protocols. . Among the new model, a branch of N's K component is expressed as n-blocks increase the arrangement from right to left, where the left column has K block on wood. Each of the two models in the two models is represented by one by one, such as: 10 = 1 2 2 5 correspondence 10 = 4 3 1 1 1 10 = 1 1 3 5 correspondence 10 = 4 2 2 1 1 10 = 1 2 3 4 corresponds to 10 = 4 3 2 1 Therefore, the total number of protocols that seek N-N-Division will be converted to the N new models to arbitrarily divide N, and the largest part of them happens to K. Solving this new model can be used to use F (a, b) to use F (a, b) to divide B, and the largest one is equal to the total number of schemes of A, which is used to do B. Any part of the division, the largest part of which is not greater than the total number of protocols, as: f (a, b) = g (a, b-a); g (a, b) = f (1, b) f (2, b) ... f (a, b); because: F (1, b) f (2, b) ... f (a, b) = f (1, b) ... f (i, b) f (A, b) (1 < = i <= a-1) f (1, b) f (2, b) .. f (a-1, b) = g (A-1, b) and so: g (a, b) = f (1, b) ... f (i, b) f (a, b) = g (A-1, b) g (a, ba) (1 <= i <= a-1) When B When A = 1, obviously G (1, b) = 1. So, according to the new model, the following recursive formula is obtained: g (a, b) = G (A-1, b) B g (a-1, b) g (a, b-a) b> = a. g (1, b) = 1. The last G (K, N-K) is asked. Reference procedure: #include
