PROBLEM LINK:
Author: Ishank Soni
Editorialist: Ishank Soni
Tester: hellb0y_suru
PROBLEM:
A string S is converted to string cipher according to the following algorithm :
Encryption (S, N )
{
cipher = S
for i → 1 to N :
j = ( i == N ) ? 1 : i+1
if ( S[i] == '1' and S[j] == '0' ) :
cipher[i] = '0'
cipher[j] = '1'
return cipher
}
You are given a cipher string. Find the number of S that will generate the given cipher string.
PREREQUISITES:
- Dynamic Programming
DIFFICULTY:
MEDIUM
EXPLANATION:
Brutally we can try all possible combinations of strings with ‘1’ and ‘0’ and check how many of them give cipher text 
Unfortunately, we can’t do this with a string of large size.
So another less intuitive solution uses dynamic programming as follows.
(Take a pen and paper, things can be a little messy down there. 
)
- Note: I have used 0 based indexing below.
We start with adding the first character of the given string to the string as the last character. i.e. cipher += cipher[0]. This will ensure that the string becomes cyclic.
First observation is that at position i in cipher string, if cipher[i] is ‘1’. Then in the original string either S[i] =1 and S[i+1] =1 or S[i -1] = 1 and S[i] = 0. Similary if cipher[i] is ‘0’. Then in the original string either S[i-1] =0 and S[i] =0 or S[i] = 1 and S[i+1] = 0. The key point here to observe is that 0 in original string may only change depanding upon previous character. While 1 in original string may only change depending upon next character.
We define a dp state dp[i][0] as the number of strings S with length i+1 and last bit ‘0’ such that S gives C, and dp[i][1] as the number of strings S with length i+1 and last bit ‘1’ such that S_{i-1} gives C_{i-1}. Here we take S_{i-1} because last bit ‘1’ may or maynot change, it depnads on ‘i+1 -th’ bit.
According to above dp[n][0] ( n is size of given string) should give total number of strings S such that size is n+1, ends at ‘0’ and S give cipher. Also note that S[n], which is last charecter must be equal to first character so, S[0] must be ‘0’. Thus dp[n][0] is the total possible strings that starts with ‘0’ and generate given cipher text.
Now dp[n][1] gives the number strings S of length n+1 such that it ends with ‘1’ and S_{n-1} give Cipher_{n-1} (which is given cipher). Also Adding or removing last ‘1’ doesn’t affect conversion of S_{n-1} to Cipher_{n-1}. Thus dp[n][1] is the total possible strings that starts with ‘1’ and generate given cipher text.
Below is how the transition in dp states could be done.
For simplicity let,
dp[i][0] = n0
dp[i][1] = n1
n0 and n1 are according to above rule.
If cipher [i] = 1, then we can add 1 to all strings i.e all n1 and n0 strings, as for n0 the last character is ‘0’ and they all already give cipher_{i} so adding ‘1’ would not affect. For n1 strings ,we can surely add ‘1’ as we want last bit of all n1 string to not change (S[i] = cipher [i] =1). Thus dp[i+1][1] = n0 + n1. Now come to adding ‘0’ at (i+1) position. We can only add ‘0’ to n0 strings only when if cipher[i+1] is ‘0’, because we can’t get ‘1’ at cipher[i+1] in given conditions. Ofcourse we can’t add ‘0’ to n1 as, this will swap last ‘1’ in n1 with 0 and we can’t get cipher[i] as 1. So if cipher [i+1] is ‘0’ dp[i+1][0] = dp[i][0] else dp[i+1][0] will be 0.
Similarly,
If cipher[i] =0 , Then we can add ‘1’ to only n0 strings, because in n1 strings last bit ‘1’ ( S[i] ) can’t change to 0. if we add ‘1’. so dp[i+1][1] = dp[i][0].Now We want to add 0, If we add ‘0’ to n1 string, then last ‘1’ at pos i will swap to pos i+1, so we must have cipher[i+1] = , And if we add ‘0’ to n1 strings then cipher[i+1] must be ‘0’. Thus if cipher[i+1] =1 then dp[i+1][0] = dp[i][1], if cipher[i+1] = 0, then dp[i+1][0] = dp[i][0].
Let ‘Ans’ be the total number of all possible original strings. ‘Ans’ may have some string that starts with ‘0’ and some string that starts with ‘1’. We can calculate them separately with base case dp[0][1] =1 for the first bit as 1 and dp[0][0] =1 for first bit as 0, finally add them together.
Do checkout the below code for better understanding.
SOLUTION:
Commented and easy code in C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
#define inf 1e17
#define _fast_ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll _power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll _power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1;a *= a; a %= mod;} return p % mod;}
ll _gcd(ll a,ll b) { return b?_gcd(b,a%b):a;}
ll _max(ll a,ll b){ if(a>b){return a;}else{ return b;}}
ll _modI(ll a, ll m){ return _power(a, m - 2, m);}
void _out(vector<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
void _out(vector<pair<ll,ll>> par ){for(auto i:par){cout<<i.first<<" "<<i.second<<"\n";}}
void _out(set<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
///////////////////////////////////////////////////////////////////////////////////////////
// Main code------------------------------
// ll mod = 998244353;
ll mod = 1000000007;
const ll N = 100000;
ll dp[N][2];
// This code will not give AC, as modulo operation is not performed.
// Only to understand easily.
void solve(){
int n;
string cipher;
ll ans = 0;
cin>>cipher;
n = cipher.size();
cipher += cipher[0];
for(int firstBit = 0; firstBit <= 1; firstBit++){
memset(dp, 0, sizeof(dp));
// Set First bit to 'firstBit' {0 or 1}.
dp[0][firstBit] = 1;
// Now calculate dp[n][firstBit] and add it to ans.
for(int i = 0; i < n; i++){
// if cipher[i] is 1 we can add '1' to all previous string Else only to string ending at 0
if (cipher[i] == '1') //11 - > 11
dp[i+1][1] += dp[i][1];
dp[i+1][1] += dp[i][0]; //01 - > 01
// Condition for adding 0.
// If cipher[i] = 1 or 0 and cipher[i+1] is 0.
if (cipher[i+1] == '0')
dp[i +1 ][0] += dp[i][0]; //00 -> 00
// If cipher[i] is 0 and cipher[i+1] is 1.
else if (cipher[i] == '0') // 10 -> 01
dp[i+1][0] += dp[i][1];
}
ans += dp[n][firstBit];
}
cout << ans << "\n";
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
setter's AC code in C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
#define inf 1e17
#define _fast_ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll _power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll _power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1;a *= a; a %= mod;} return p % mod;}
ll _gcd(ll a,ll b) { return b?_gcd(b,a%b):a;}
ll _max(ll a,ll b){ if(a>b){return a;}else{ return b;}}
ll _modI(ll a, ll m){ return _power(a, m - 2, m);}
void _out(vector<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
void _out(vector<pair<ll,ll>> par ){for(auto i:par){cout<<i.first<<" "<<i.second<<"\n";}}
void _out(set<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
// ll mod = 998244353;
ll mod = 1000000007;
const ll N = 100000;
ll dp[N][2];
void solve(){
int n;
string s;
ll ans = 0;
memset(dp,0,sizeof(dp));
cin>>s;
n = s.size();
s+= s[0];
dp[0][1] = 1;
f(n){
if(s[i] == '1')
dp[i+1][0] = dp[i][0] + dp[i][1];
else
dp[i+1][0] = dp[i][1];
if (s[i] =='0' && s[i+1] == '1')
dp[i+1][1] = dp[i][0];
else if (s[i+1] == '0')
dp[i+1][1] = dp[i][1];
dp[i+1][0] %= mod;
dp[i+1][1] %= mod;
}
ans += dp[n][1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// cout<<ans<<"\n";
f(n){
if (s[i]=='1')
dp[i+1][0] = dp[i][0] + dp[i][1];
else
dp[i+1][0] = dp[i][1];
if (s[i] == '0' && s[i+1] == '1')
dp[i+1][1] = dp[i][0];
else if (s[i+1] == '0')
dp[i+1][1] = dp[i][1];
dp[i+1][0] %= mod;
dp[i+1][1] %= mod;
}
ans += dp[n][0];
ans %= mod;
cout<<ans<<"\n";
return;
}
int main()
{
int t;
cin>>t;
while(t--){
solve();
}
}
Feel free to ask any query. If the given explanation is confusing we can discuss it 
Hope you like the Problem and editorial.