find pattern

In the defined Fibonacci sequence $$$s$$$, initially established with $$$s_0$$$ = ‘0’ and $$$s_1$$$ = ‘1’ , concatenating the last string with the second-to-last string yields alternating parity. consequently, for $$$s_i$$$ , if $$$i$$$ is even, the parity of $$$s_i$$$ is even, and if $$$i$$$ is odd, the parity of $$$s_i$$$ is odd.

Upon observation, it's evident that the function $$$f(s)$$$ generates the Fibonacci sequence starting from $$$f(s_2)$$$ . Given the established fact that every third Fibonacci number is even, we can conclude that $$$f(s)$$$ is even for $$$s$$$ = $$$s_{2+3i}$$$ and odd otherwise .

Now we got parity for nth element of both $$$s$$$ and $$$f(s)$$$ , compare parity of both and answer .

#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;

const int N=1e5;


void solve(){
    int n;
    cin >> n;
    bool s = ((n%2)==0);
    bool fs = ((n%3)==2);

    if(s == fs){
       cout << "YES";
    }else cout << "NO";

    cout << endl;
}

signed main() {
    fastio();

    int t = 1;
    cin >> t;
    while(t--){
        solve();       
       }
    return 0;
}

prefix and suffix

#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;

const int N=1e5;

void solve(){
    int m, n;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int index = 0;
    s.insert(0, "0"); t.insert(0, "0");
    vector<int> pre(n + 1), suff(n + 2);
    for(int i = 1; i <= n; i++) {
        if(s[i] == t[index + 1] and index<m)
            index++;
        pre[i] = index;
    }
    suff.back() = index = t.size();
    for(int i = n; i > 0; i--) {
        if(s[i] == t[index - 1] and index>1) 
            index--;
        suff[i] = index;
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        if(suff[r + 1] - pre[l - 1] < 2)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

signed main() {
    fastio();

    int t = 1;
    while(t--){
        solve();       
       }
    return 0;
}

Try to use DP to solve this problem

Let $$$dp[i][p][q][turn]$$$ denote the probability of Rajat winning the game, where:

• $$$i$$$ denotes the number of turns left,
• $$$p$$$ denotes the parity of Rajat’s score,
• $$$q$$$ denotes the parity of Dr. S’s score, and
• $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.

Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing even and odd elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.

The transitions will be as follows:

If it is Rajat’s turn, then there are 2 additional cases:

Case 1: When $$$a_n$$$ is odd

Case 2: When $$$a_n$$$ is even

Similarly, for Dr. S’s turn:

Case 1: When $$$a_n$$$ is odd

Case 2: When $$$a_n$$$ is even

where $$$p_n$$$ is the probability of rolling $$$n$$$.