ABC 202

Table of Contents

D - aab aba baa

https://atcoder.jp/contests/abc202/tasks/abc202_d

はじめの文字が a となる場合の数は $A-1$ 個の a と $B$ 個の b の並び替え方の場合の数だから $\frac{(A+B+1)!}{(A-1)!B!}$ である。 よって $K > \frac{(A+B+1)!}{(A-1)!B!}$ のときは b から始まる。

この性質を使って先頭から文字を決めていく。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b, k;
    cin >> a >> b >> k;

    int m = a + b;
    vvll dp(m + 1, vll(m + 1, 0));
    dp[0][0] = 1;
    rep(i, m + 1) {
        rep(j, m + 1) {
            if (i > 0)
                dp[i][j] += dp[i - 1][j];
            if (j > 0)
                dp[i][j] += dp[i][j - 1];
        }
    }

    string ans = "";
    auto dfs = [&](auto dfs, ll na, ll nb, ll rem) {
        if (na == 0 && nb == 0) {
            return;
        }

        if (na == 0) {
            ans.push_back('b');
            dfs(dfs, na, nb - 1, rem);
            return;
        }
        if (nb == 0) {
            ans.push_back('a');
            dfs(dfs, na - 1, nb, rem);
            return;
        }

        ll v = dp[na - 1][nb];
        if (rem <= v) {
            ans.push_back('a');
            dfs(dfs, na - 1, nb, rem);
            return;
        }

        ans.push_back('b');
        dfs(dfs, na, nb - 1, rem - v);
    };

    dfs(dfs, a, b, k);

    cout << ans << endl;
}