小易的字典【排列组合】

题目链接：

很明显按照字典序排序选取，第n个字符串，很容易想到这道题目需要用到排列组合来模拟运算，不过用python3来写比用c++来写简化很多的细节，实现起来相对来说简单了很多

def Cnm(a, b):
    ans = 1
    for i in range(a + 1, a + b + 1):
        ans *= i
    for i in range(1, b + 1):
        ans //= i
    return ans


n, m, k = map(int, input().strip().split())
if Cnm(n, m) < k:
    print(-1)
else:
    ans = ""
    while n > 0 and m > 0:
        temp = Cnm(n - 1, m)
        if temp < k:
            k -= temp
            ans += "z"
            m -= 1
        else:
            ans += "a"
            n -= 1
    ans += "a" * n
    ans += "z" * m
    print(ans)

解题思路:

排列组合，n个a和m个z，只能组成$C_{n+m}^n$，记为count(n+m,n) 个单词。

思路：

假设第一个字符为a，则剩下n-1个a和m个z组成的子序列只能构成count(n-1+m,n-1)个单词，且是字典中前count(n-1+m,n-1)个单词。 比较k和count(n-1+m,n-1)，若k小，说明k是前count(n-1+m,n-1)个单词，则第一个字符必为a。子问题化为在子序列(n-1个a和m个z)找到第k个单词 若k大，则说明第一个字符必为z,单词是以z开头的单词中的第k-count(n-1+m,n-1)个。子问题化为在子序列(n个a和m-1个z)找到第k-count(n+m-1,m-1)个单词。

eg:n=2,m=2,k=5

假设第一个字符为a,则剩下1个a,2个z只能构成3个单词，且是字典中前3个单词(aamm,amam,amma) k>3，则第一个字符必为z。原问题化为在n=2,m=1,k=2，即在剩下2个a，1个z中找到第2个单词

#include<iostream>
    #include<vector>
    using namespace std;
     
    void fun(int n, int m, long long k) {
        vector<char> vec;
        while (n && m) {
            //每次迭代问题规模缩减一个单位
            //排列组合:假设当前序列首字符为a，剩下n-1个a放在剩下n - 1 +m 个位置共有的可能数
            long long count = 1;
            for (int i = 0; i < n - 1; i++) {//求组合数
                count *= (n - 1 + m - i);
                count /= (i + 1);
                if (count > k)//求count的过程中可能数太大造成越界变为负数,所以当count>k直接跳出
                    break;
            }
     
            if (k <= count)//如果k小于等于count，则表明首字符的确应为a
            {
                n--;//问题缩减为 n-1个a和m个z 中找第k大
                vec.push_back(a);
            }
            else//当前位是z
            {
                m--;//问题缩减为 n-1个a和m个z 中找第k-count大
                k -= count;
                vec.push_back(z);
            }
        }
     
        //循环结束后，剩余子序列只存在"aa..aaa" 或 "zz..zzz"1种情况
        if (k != 1) {
            cout << -1;
            return;
        }
     
        while (n--) vec.push_back(a);
        while (m--) vec.push_back(z);
     
        for (auto it : vec) {
            cout << it;
        }
     
    }
     
    int main() {
        int n, m;
        long long k;
        cin >> n >> m >> k;
     
        fun(n, m, k);
     
        return 0;
    }