C - Duodecim Ferra Editorial by en_translator


If we brute force all the possible combinations of dividing positions, it will take \(\Theta(L^{12})\) time, which is too long for the time limit. Let’s consider better way.
First, we should choose the positions where the distances from the western end are integers, so that the lengths of resulting bars will be positive integers. Conversely, if we cut the bar at the positions where the distances from the western end are integers, then each of the divided bars will have an integer length.
Therefore, it is sufficient to find the number of combinations of \(11\) positions out of \(L - 1\) candidates of cutting positions.
This is equal to \(_{L - 1}C_{11} = \frac{(L - 1)(L - 2)(L - 3) \dots (L - 11)}{11!}\).
Note that, although the value of fraction itself is less than \(2^{63}\), the numerator may not fit in a \(64\)-bit integer. There are several ways to avoid overflows:

  • Calculate using Pascal’s triangle
    \(_iC_j\) is written in the \(j\)-th (0-indexed) position in the \(i\)-th (0-indexed) row in the Pascal’s triangle.
    On the other hand, when you calculate Pascal’s triangle by definition, none of the intermediate values while calculating \(_iC_j\) does not exceed \(_iC_j\), so we can avoid overflows.
    However, even if \(_iC_j\) does not overflow, some of \(_iC_j\) may overflow if it is not needed to be calculated. (e.g. \(_{199}C_{11} < 2^{63}\), but \(_{199}C_{100} > 2^{190}\))
    In such case, in languages like C++, if you use signed integers, the entire behavior of the program will be immediately undefined, even if the overflowed value does not affect the answer.
  • Calculate while divide accordingly
    Calculate in the order of \(\frac{(L - 1)}{1!}, \frac{(L - 1)(L - 2)}{2!}, \frac{(L - 1)(L - 2)(L - 3)}{3!}, \dots, \frac{(L - 1)(L - 2)(L - 3) \dots (L - 11)}{11!}\). The values here are \(_{L - 1}C_1, _{L - 1}C_2, _{L - 1}C_3, \dots, _{L - 1}C_{11}\), which are all integers. Also, we can calculate by \(_{L - 1}C_{(i + 1)} = \frac{_{L - 1}C_i \times (L - (i + 1))}{(i + 1)}\).
    The maximum intermediate values are \(_{199}C_{11} \times 11\), which is less than \(2^{63}\), so it won’t overflow.
  • Use \(128\)-bit integers Some languages and environments has \(128\)-bit integer type, and the numerator fits in a \(128\)-bit integer, so we can avoid overflows by using this. (e.g. In AtCoder C++, we can use __int128 type)

posted:
last update: