The Question in the link below was asked in the Code Monk Round at hackerearth
https://www.hackerearth.com/problem/algorithm/vaishu-and-best-friends/
I decoded it and found that the answer should be
(all possible combination - All subsequences with alernating 0s and 1s)
So the Problem narrows down to finding the number of possible subsequences with alternating 0s and 1s
here is my approach of finding all possible subsequences with alternating 0s and 1s
dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
if(i % 2 == 1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}
Here dp[0][i] indicates all the subsequences till now ending at a 0
and dp[1][i] indicates all the subsequences till now ending at a 1
The sum of dp[0][n] + dp[1][n] will tell all alternating subsequences
But i am getting a wrong answer.
Please Point out what is wrong
Here is the Full code
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long dp[2][1000005];
long long power[1000005];
void precompute(){
power[0] = 1;
power[1] = 2;
dp[1][1] = 1;
dp[0][1] = 0;
for(int i = 2; i <= 1000000; i++){
power[i] = power[i-1]*2;
power[i] %= M;
if(i&1){
dp[1][i] = (dp[0][i-1] + dp[1][i-1] + 2)%M;
dp[0][i] = (dp[0][i-1]%M);
}else{
dp[0][i] = (dp[1][i-1] + dp[0][i-1] + 1)%M;
dp[1][i] = (dp[1][i-1]%M);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
precompute();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("&d", &n);
long long ans = ((M + ((power[n] - dp[0][n-1] + M) % M) - dp[1][n-1]))%M ;
ans += M;
ans %= M;
printf("%d\n", ans);
}
return 0;
}