Nondecreasing Numbers
Time limit1sMemory limit128 MB
Count the number of n-digit strings (digits 0-9, leading zeros allowed) that are nondecreasing, for n up to 64 requiring big integers.
- Level
Medium4 of 10
- Topics
- Combinatorics, Math
- Solved
- No attempts yet
Problem
A number is nondecreasing if, when read from left to right, no digit is smaller than the digit immediately before it.
For example, 1234 is nondecreasing.
Some nondecreasing 4-digit strings are 0011, 1111, 1112, 1122, and 2223. There are 715 nondecreasing 4-digit strings in total.
Leading zeroes are allowed in this problem. Therefore, 0000, 0001, and 0002 are valid nondecreasing 4-digit strings.
Given n, write a program that computes the number of nondecreasing n-digit strings.
Input
The first line contains the number of test cases T (1 <= T <= 1,000).
Each test case consists of one integer n (1 <= n <= 64).
Output
For each test case, output the number of nondecreasing n-digit strings on its own line.