Problem A: Digit Frequency Analysis

Given a functon (f(x)) that counts the frequency of the most common digit in number (x), compute (\sum_{i=l}^{r}f(i)) for large ranges (up to (10^{18})).

Approach:

• Represent digit counts as a state vector (S = {c_0, \dots, c_9})
• Transform into frequency-of-counts representation (S' = {a_0, \dots, a_{18}})
• Use digit DP with approximately 1477 unique states

Problem B: Distinct Subsequence Counting

Given parameters (n) and (m), count distinct subsequences in a specific peroidic sequence pattern.

Key Insight:

• Dynamic programming with recurrence: [f_i = \sum_{j=i-m}^{i-1}f_j]
• Convert to prefix sums (s_i): [s_i = 2s_{i-1} - s_{i-m-1}]
• Closed-form solution using combinatorial enumeration: [s_n = \sum_{k=0}^{\lfloor n/(m+1)\rfloor}(-1)^k \cdot 2^{n-(m+1)k} \cdot \binom{n-(m+1)k+k}{k}]

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int main() {
    int n, q, m;
    cin >> n >> q;
    vector<int> dp(n+1), fact(n+1), inv(n+1);
    
    // Precompute factorials and modular inverses
    fact[0] = inv[0] = 1;
    for(int i=1; i<=n; i++) 
        fact[i] = 1LL*fact[i-1]*i%MOD;
    inv[n] = pow(fact[n], MOD-2, MOD);
    for(int i=n-1; i>0; i--)
        inv[i] = 1LL*inv[i+1]*(i+1)%MOD;
    
    auto comb = [&](int a, int b) {
        return 1LL*fact[a]*inv[b]%MOD*inv[a-b]%MOD;
    };
    
    // Precompute answers for all m
    for(int i=1; i<=n; i++) {
        for(int k=0; k<=n/(i+1); k++) {
            int term = 1LL * (k%2 ? -1 : 1) * pow(2, n-(i+1)*k, MOD) * comb(n-i*k, k) % MOD;
            dp[i] = (dp[i] + term + MOD) % MOD;
        }
    }
    
    while(q--) {
        cin >> m;
        cout << dp[m] << '\n';
    }
}

Problem C: Knight's Tour on Infinite Plane

Determine how many pairs ((a,b)) allow a knight with moves (a×b) to visit every integer point.

Solution:

• Valid when (\gcd(a,b)=1) and (a+b) is odd
• Formula reduces to: [2\sum_{\substack{a\leq n/2\b\leq n\a\perp b\b\text{ odd}}}1]
• Efficient computation using Möbius function and inclusion-exclusion

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

const int MAX = 2e7;
vector<int> mu(MAX+1);

void sieve() {
    vector<bool> prime(MAX+1, true);
    mu[1] = 1;
    for(int i=2; i<=MAX; i++) {
        if(prime[i]) {
            for(int j=i; j<=MAX; j+=i) {
                prime[j] = false;
                mu[j] = (j/i)%i ? -mu[j/i] : 0;
            }
        }
    }
    partial_sum(mu.begin(), mu.end(), mu.begin());
}

ll coprime_pairs(ll n, ll m) {
    if(n > m) swap(n, m);
    ll res = 0;
    for(ll i=1, j; i<=n; i=j+1) {
        j = min(n/(n/i), m/(m/i));
        res += (mu[j]-mu[i-1])*(n/i)*(m/i);
    }
    return res;
}

ll solve(ll n) {
    if(n == 0) return 0;
    return coprime_pairs(n/2, n) - solve(n/2);
}

int main() {
    sieve();
    int T; cin >> T;
    while(T--) {
        ll n; cin >> n;
        cout << 2*solve(n) << '\n';
    }
}

Problem H: Grid Path with Value Reduction

Compute expected final value when moving through a grid with special points that halve the value.

Approach:

1. Sort special points
2. Dynamic programming with states tracking:
   • Current position
   • Number of special points visited
3. Combine using binomial coefficients for path counting
4. Handle large (s) by capping at (\log_2(s)) reductions

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int main() {
    int n, m, k, s;
    cin >> n >> m >> k >> s;
    
    vector<pair<int,int>> pts(k+2);
    pts[0] = {1,1}; pts[k+1] = {n,m};
    for(int i=1; i<=k; i++) 
        cin >> pts[i].first >> pts[i].second;
    sort(pts.begin()+1, pts.end()-1);
    
    vector<vector<ll>> dp(k+2, vector<ll>(22));
    dp[0][0] = 1;
    
    for(int i=1; i<=k+1; i++) {
        for(int j=0; j<i; j++) {
            if(pts[j].first > pts[i].first || pts[j].second > pts[i].second) continue;
            int dx = pts[i].first - pts[j].first;
            int dy = pts[i].second - pts[j].second;
            ll paths = comb(dx+dy, dx);
            for(int p=1; p<=21; p++)
                dp[i][p] = (dp[i][p] + dp[j][p-1]*paths) % MOD;
        }
    }
    
    vector<int> values(22);
    values[1] = s;
    for(int i=2; i<=21; i++)
        values[i] = (values[i-1]+1)/2;
    
    ll total = comb(n+m-2, n-1);
    ll result = 0;
    for(int i=1; i<=21; i++) {
        result = (result + dp[k+1][i]*values[i]) % MOD;
        total = (total - dp[k+1][i] + MOD) % MOD;
    }
    result = (result + total) % MOD;
    
    cout << result * inv(comb(n+m-2,n-1)) % MOD << '\n';
}