算法
(组合) $O(3600)$
如果按字典顺序对其进行排序,则其顺序将为
a????????
b????????
,并考虑其为 Kth
,则我们可以考察这个字符串属于哪个组。
对于以字符 'a'
开始的字符串的组合数为 $\binom{a + b - 1}{a - 1}$,不妨记为 $x$,若 $k \leqslant x$,就选择 'a'
,并 --a
,否则选择 'b'
,并 --b
,这意味着跳过了 $a????????$,所以 $K$ 将减掉 $x$,然后一直循环这个过程直到 $a + b = 0$ 为止。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::string;
using ll = long long;
ll c[61][61];
int main() {
int a, b;
ll k;
cin >> a >> b >> k;
c[0][0] = 1;
rep(i, 60) {
rep(j, i + 1) {
c[i + 1][j] += c[i][j];
c[i + 1][j + 1] += c[i][j];
}
}
string ans;
while (a + b) {
ll x = 0;
if (a >= 1) x = c[a + b - 1][a - 1];
if (k <= x) {
ans += 'a';
--a;
}
else {
ans += 'b';
--b;
k -= x;
}
}
cout << ans << '\n';
return 0;
}