UVa 10943

From Algorithmist
Jump to navigation Jump to search

10943 - How do you add?[edit]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1884

Summary[edit]

Find the number of ways to form Number N from the addition of K numbers less than N.

Explanation[edit]

Observing that the number of ways are N+K-1 C K-1, we precompute the values and answer query in O(1).

Gotchas[edit]

Output is mod 1e6.

Input[edit]

63 59
100 100
0 0

Output[edit]

649440
420660

Solutions[edit]