Soluție HackerRank pentru String Modification, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: String Modification
  • Domeniu: Combinatorics
  • Limbaj: C++14

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

Cerință

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`<·s<`X`<`Y`<`Z`<`_`

Input Format

The first line contains two space separated integers n ( 1 ≤ n ≤ 10^9) and k ( 0 ≤ k ≤ 10^9). The second line contains string s containing only uppercase English letters ( 1 ≤ |s| ≤ 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 sursă

#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;
}
HackerRank Combinatorics – String Modification