HackerRank Combinatorics – String Modification

Challenge: String Modification

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 150.0 / 150

Submission status: Accepted

Submission score: 1.0

Submission ID: 464818299

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/string-modification/problem

Cerinta

Roy was given a string $s$ containing only uppercase English letters. He can do any number of modifications on $s$. The allowed modifications are:

1. He can add underscore ('`_`') character in anywhere inside the string.  
2. He can delete any existing character of the string.  
3. He can swap any two characters of the string.

Every character in the resulting string has a value equal to its ASCII value.

After doing the modifications the string needs to have the following properties:

1. The length of the string should be equal to $n$.  
2. There should be at least $k$ characters of higher value between two equal letters (Note that, underscore is not a letter).

Calculate how many different strings Roy can achieve **modulo** $1000003~(10^{6}+3)$.

Note: _In the increasing order of ASCII value, we can arrange the alphabet in the following way,_  
`A`<`B`<`C`<`D`<$\cdots$<`X`<`Y`<`Z`<`_`

**Input Format**

The first line contains two space separated integers $n$ $( 1 \le n \le 10^9)$ and $k$ $( 0 \le k \le 10^9)$. The second line contains string $s$ containing only uppercase English letters $( 1 \le |s| \le 2500)$.

**Output Format**

Print the number of different strings Roy can achieve modulo $1000003~(10^{6}+3)$.

**Sample Input #1**  

    3 1
    LBB
    
**Sample Output #1** 

    15
    
**Sample Input #2**  

    5 2
    PPPP
    
**Sample Output #2**

    9
    
**Sample Input #3**  

    8 7
    DQ
    
**Sample Output #3**

    73
    
**Sample Input #4**  

    1078 223
    RMXQYQPKSSBJCAFWPXZ
    
**Sample Output #4**

    451838
    
**Explanation**

In the first test case, the 15 valid strings are  
`BLB`  
`BL_`  
`B_B`  
`B_L`  
`B__`  
`LB_`  
`L_B`  
`L__`  
`_BL`  
`_B_`  
`_LB`  
`_L_`  
`__B`  
`__L`  
`___`

Cod sursa

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

static const int MOD = 1000003; // prime

static int mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return (int)r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, K;
    string s;
    if (!(cin >> n >> K)) return 0;
    cin >> s;

    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'A']++;
    int M = (int)s.size();

    // Precompute factorials up to MOD-1 for O(1) nCk when k < MOD.
    static vector<int> fact, invfact;
    fact.assign(MOD, 1);
    invfact.assign(MOD, 1);
    for (int i = 1; i < MOD; ++i) fact[i] = (long long)fact[i - 1] * i % MOD;
    invfact[MOD - 1] = mod_pow(fact[MOD - 1], MOD - 2);
    for (int i = MOD - 1; i >= 1; --i) invfact[i - 1] = (long long)invfact[i] * i % MOD;

    auto C_small = [&](int N, int R) -> int {
        if (R < 0 || R > N) return 0;
        return (long long)fact[N] * invfact[R] % MOD * invfact[N - R] % MOD;
    };

    // Lucas simplification for k < MOD: C(bigN, k) mod MOD = C(bigN % MOD, k) if k <= bigN%MOD else 0.
    auto C_big_k_small = [&](long long bigN, int k) -> int {
        if (k < 0) return 0;
        if (bigN < 0) return 0;
        int n0 = (int)(bigN % MOD);
        if (k > n0) return 0;
        return C_small(n0, k);
    };

    vector<int> dp(M + 1, 0), ndp(M + 1, 0);
    dp[0] = 1;

    int usedSoFarMax = 0;

    for (int ch = 0; ch < 26; ++ch) {
        int f = freq[ch];
        if (f == 0) continue;

        fill(ndp.begin(), ndp.end(), 0);

        for (int h = 0; h <= usedSoFarMax; ++h) {
            int waysBase = dp[h];
            if (!waysBase) continue;

            for (int x = 0; x <= f; ++x) {
                int h2 = h + x;
                if (h2 > M || h2 > n) break;

                long long H = n - h2; // number of higher chars (future letters + underscores)
                long long top;
                if (x == 0) {
                    top = 0; // C(0,0)=1
                } else {
                    // W(H,x) = C(H + 1 - (x-1)*(K-1), x)
                    top = H + 1 - 1LL * (x - 1) * (K - 1);
                }

                int comb;
                if (x == 0) comb = 1;
                else comb = C_big_k_small(top, x);
                if (!comb) continue;

                ndp[h2] = (ndp[h2] + (long long)waysBase * comb) % MOD;
            }
        }

        usedSoFarMax += f;
        for (int i = 0; i <= usedSoFarMax; ++i) dp[i] = ndp[i];
    }

    int ans = 0;
    for (int h = 0; h <= M; ++h) {
        ans += dp[h];
        if (ans >= MOD) ans -= MOD;
    }

    cout << ans << '\n';
    return 0;
}