Given a set of K distinct characters.
Find the number of ways to create a string of length N.
Given that-
1.No 2 adjacent character should be same
2.Odd positions can be filled by any one of the K characters.
3.Even positions can be filled by any character from a-z.
Since answer can be large print it in modulo 10^9+7.
Constraints:-
1<=N<=10^5
0<=K<=26
Example:-
N=2,K=1
a
Output:-
25
From hackerearth right,
yes, I am so bad at combinatorics.
Me toooo ( kha jaao 20 char ko ),
just do dp,
where dp[i][j] , is the number of ways to create a string of length i , taking j’th charater
I think this problem can be easily solved using DP, mostly because of the 1st condition.
Lets denote memo[len][last] as the number of strings with length len and that end in letter last.
Now, we can build the number of strings that end in last according to the parity of len:
The only condition left is the 1st one, which means that:
memo[len][last] = \sum\limits_{before \in \Sigma, before \neq last} memo[len-1][before]
Where \Sigma is the english alphabet.
But this makes us to make an extra iteration over all before values (therefore, our complexity would be O(n\Sigma^{2})), but this can be avoided by noticing this:
memo[len][last] = (\sum\limits_{before \in \Sigma} memo[len-1][before] ) - memo[len-1][last]
But how does this help? In fact, we can preprocess the sum value at the end of procesing the length len and storing it in the value prevSum, so for the next iteration we’ll have:
memo[len][last] = prevSum - memo[len-1][last]
Finally, our answer would be the number of strings with length n that can end in any character, thus
ans = \sum\limits_{c \in \Sigma} memo[n][c]
Our complexity will be O(n\Sigma).
Be sure to take more at every calculation…
there were test cases involved hence we required constant time ans, i did dp got tle
This is a DP + combinatorics problem.
For first position you have k choices. After that,
1.) For even there are two cases:
a) if the previous character was from the given k characters, you have k-1 choices
b) if the previous character was other than the given k characters, you have 26-k choices.
2.) For Odd there are two cases:
a) if the previous character was from the given k characters, you have k-1 choices
b) if the previous character was other than the given k characters, you have k choices.
Complexity: O(N) per test case
C++ code
My solution was without using dp. By observing carefully(and of course doing the combinatorics stuff), we get the relation depending upon n and k. For even length string, it is 25 * k * (p^(n/2 - 1)) and for odd length string it is (p^(n/2)) * k where p is (k-1) * (k-1) + k * (26-k).
My 100AC solution.
Complexity: O(logn) for each test case. (for modular exponentiation).
It would be better if you could explain how you reached that formula.
Can you tell me what the number of testcases ?
The number of testcase T was between 1 and 250
So my lovely dp wont work. Let me cry.
Well O(N*T) = 2.5 * 10^7
This should pass 1 second time limit but we will get TLE due to too many modulo operations.
You derived eqn after such a long work in a 2- hour contest where there were 2 more problems to be solved… Kudos to you!!! Any tips for noobies like me to improve math?
yeah I follow @anon55659401 and other legendary coders. I am a complete noob and that’s how I’m learning. You can do the same. 
just to make matter worse time limit was 0.5 seconds.
Enjoy!!
O(N) solution gave AC verdict during contest
