Truth Transmission

Author: knishanthreddy

Required Knowledge : Digit Dp

Time Complexity : $\mathcal{O}(T\cdot 10^3)$

Editorialist : knishanthreddy

Approach:

First, let's understand what makes a Time Code good.

In each Time Code, only the guardians marked with odd digits flip the message. Therefore, for the message to remain unchanged, the total number of odd digits in the sequence must be even.

Since $L$ and $R$ can be extremely large $($up to $10^{100})$ digits, iterating over all Time Codes in the range $[L,R]$ is impossible.

Hence, we use Digit DP, which allows us to count valid Time Codes digit by digit efficiently.

The DP state is: dp$[$pos$][$tight$][$parity$]$

$\bullet$ pos: current digit index

$\bullet$ tight: whether the current prefix matches the upper bound

$\bullet$ parity: whether the count of odd digits so far is even $(0)$ or odd $(1)$

In digit dp, the tight variable will tell if the current digits range is restricted or not. If the current digit's range is not restricted then it will span from $0$ to $9$ $($inclusively$)$ else it will span from $0$ to limit$[$idx$]$ (inclusively).

At each position, we try all possible digits $d$ from $0$ to the allowed limit:

$\bullet$ If $d$ is odd: it flips the parity.

$\bullet$ If $d$ is even: parity stays the same.

$\bullet$ If tight is $1$ and $d$ equals the upper limit digit, next state remains tight.

When all digits are processed $($Base Case$)$:

$\bullet$ If parity is even, return $1 ($good Time Code$)$.

$\bullet$ Otherwise, return $0$.

To find the total good Time Codes in range $[L, R]$:

$\bullet$ Compute countGood$(R)$: good Time Codes from $0$ to $R$.

$\bullet$ Compute countGood$(L−1)$: good Time Codes from $0$ to $L−1$.

Final answer = $($countGood$(R)$− countGood$(L−1)$ $+$MOD$)$ $\%$ MOD.

Setter's Code:

// C++

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
template<class T>
void input(vector<T> &a) {
    for(auto &e:a)
        cin >> e;
}
const int M=1e9+7;
int dp[110][2][2];

// fun(index, tight, parity)
int fun(string &num,int idx,bool tight,bool parity) {
    if(idx==num.size()) {
        return !parity;
    }
    
    int &res=dp[idx][tight][parity];
    
    if(res!=-1) return res;
    
    int ub=tight?(num[idx]-'0'):9;
    res=0;
    
    for(int i=0;i<=ub;i++) {
        res=(res+fun(num,idx+1,tight&(i==ub),parity^(i&1)))%M;
    }
    
    return res;
}

//Subract 1 from the big number represented by s
string sub1(string s) {
    int n=s.size();
    for(int i=n-1;i>=0;i--) {
        if(s[i]>'0') {
            s[i]--;
            break;
        }
        else s[i]='9';
    }
    if(s.size()>1 && s[0]=='0') {
        return s.substr(1);
    }
    return s;
}

void solve()
{       
    string l,r;
    cin >> l >> r;
    l=sub1(l);
    memset(dp, -1, sizeof(dp));
    
    // number of good time codes from 0 to R 
    int rans=fun(r,0,1,0);
    memset(dp,-1,sizeof(dp));
    
    // number of good time codes from 0 to L-1
    int lans=fun(l,0,1,0);
    
    cout << (rans-lans+M)%M << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

Tester's Code:

//Python

MOD = 10**9 + 7

def count_valid(num):
    s = str(num)
    n = len(s)

    dp = [[[-1 for _ in range(2)] for _ in range(2)] for _ in range(n+1)]

    def fun(idx, tight, parity):
        if idx == n:
            return int(parity == 0)
        
        if dp[idx][tight][parity] != -1:
            return dp[idx][tight][parity]
        
        ub = int(s[idx]) if tight else 9
        res = 0
        for i in range(ub + 1):
            res = (res + fun(idx + 1, tight and (i == ub), parity ^ (i & 1))) % MOD
        
        dp[idx][tight][parity] = res
        return res

    return fun(0, 1, 0)


def main():
    t = int(input())
    for _ in range(t):
        l, r = map(int, input().split())
        ans = (count_valid(r) - count_valid(l - 1) + MOD) % MOD
        print(ans)


if __name__ == "__main__":
    main()