LongWordsDiv1
SRM 618 · 2013-12-22 · by ltaravilse
SRM 618 · 2013-12-22 · by ltaravilse · Advanced Math, Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
Fox Ciel uses an alphabet that has n letters. She likes all the words that have the following properties:
int n, compute and return the number of words Ciel likes, modulo 1,000,000,007.
- Equal letters are never consecutive.
- There is no subsequence of the form xyxy, where x and y are (not necessarily distinct) letters. Note that a subsequence doesn't have to be contiguous.
- There is no longer word with properties 1 and 2.
- Ciel does not like "ABBA" because there are two consecutive 'B's.
- Ciel does not like "THETOPCODER" because it contains the subsequence "TETE".
- Ciel does not like "ABACADA" because it contains the subsequence "AAAA". (Note that here x=y='A'.)
- Ciel does not like "ABCA" because "ABCBA" is longer.
- If n=1 and the one letter Ciel uses is 'A', then she likes the word "A".
- If n=2 and the two letters Ciel uses are 'A' and 'B', then she likes the words "ABA" and "BAB".
Constraints
- n will be between 1 and 5000, inclusive.
Examples
0)
1 Returns: 1
The only word Ciel likes is "A" (assuming 'A' is the only letter in the alphabet).
1)
2 Returns: 2
The words Ciel likes are "ABA" and "BAB".
2)
5 Returns: 1080
3)
100 Returns: 486425238
Don't forget to compute the answer modulo 1,000,000,007.
4)
3191 Returns: 477311902
Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LongWordsDiv1 with a public method int count(int n) · 46 test cases · 2 s / 256 MB per case