1, 2, 3 Sum 8
InterviewTime limit1sMemory limit512 MB
For each n, count the ordered compositions of n into parts 1, 2, 3, reporting the number using an odd count of terms and the number using an even count, each modulo 1,000,000,009.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Math, Combinatorics
- Solved
- No attempts yet
Problem
There are 7 ways to express the integer 4 as a sum of 1, 2, and 3. When forming a sum, you must use at least one number.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
Given an integer n, write a program that finds the number of ways to express n as a sum of 1, 2, and 3.
Input
The first line gives the number of test cases T. Each test case occupies one line and gives an integer n. n is a positive integer less than or equal to 100,000.
Output
For each test case, print the number of ways whose number of terms used is odd and the number of ways whose number of terms used is even, separated by a space.
The counts must be printed modulo 1,000,000,009.