Dhoni and the beautiful strings
All submissions for this problem are available.
This time Dhoni has developed a passion for strings. Dhoni has an integer N and infinite supply of the characters 'A','B' and 'C'. Dhoni wants to know how many beautiful strings of length N can be generated by using these characters. A string is considered as beautiful if it does not have "ABC" as its substring. But he does not know how to code so he is asking you to help him. Since this number may be quite large, output the answer modulo 109 + 7.
- First line of input contains the number of test cases T.
- Each of next T lines contain an integer N.
- For each test case, output the number of beautiful strings of length N.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
Input : 2 2 3 Output : 9 26
- In the 1st test case, all 9 possible strings are beautiful as none of them have "ABC" as a substring. Hence the answer is 9.
- In the 2nd test case, total 27 strings of length 3 are possible and only string “ABC” is not beautiful. Hence the answer is 26.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions