【SSL 1967】A和B

题目大意

有一个字符串是由 $m$ 个 ${}^{\prime }{a}^{\prime }$ 和 $n$ 个 ${}^{\prime }{b}^{\prime }$ 字母组成的。求所有这样的字符串中，字典序第 $k$ 小的字符串是哪个？

数据范围:
对于 $15\%$ 的数据，$1\le m,n\le 2$；
对于 $25\%$ 的数据，$1\le m,n\le 10$；
对于 $100\%$ 的数据，$1\le m,n\le 30,1\le k\le C_{m+n}^m$。

输入格式

输入三个数：$m$ $n$ $k$，中间用空格分割。

输出格式

输出对应的字符串。

输入样例

2 2 4

输出样例

baab

基本思路

这题乍一看应该是康托展开，但又发现有不对劲的地方，这题的序列并不是数字。但是我们可以沿用康托展开的思想。

我们就拿样例分析：
首先我们在第一个位置填 $a$ 然后我们还剩一个 $a$ 可用，在剩下三个位置把它填上，一共有 $3$ 种可能，可是我们要字典序为 $4$ 的序列，第一个填 $a$ 显然不行，所以第一个位置填 $b$。
第一个填完看到第二个，还是先尝试填 $a$ ，此时已经排除第一位填 $a$ 的$3$ 种可能，我们将 $k$ 减 $3$ 变为 $1$，我们在剩下两个位置中填剩下一个 $a$ ，有 $2$ 种可能，明显 $k$ 就是在这个范围内的，以此类推即可。

然后就是处理计算排列组合的问题了，如果我们现用现算阶乘一定会超时，可是预处理结成会炸变量，所以仔细看看代码中的注释是如何处理的。

核心代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull m,n,k,C[100][100],index,tmp;
int main(){
	ios::sync_with_stdio(false);
	cin>>m>>n>>k;
	C[0][0]=1;
	//C(n,m)为在n个数中选取m个数的组合数
	//C(n,m)=C(n-1,m)+C(n-1,m-1)
	//可以理解为是否选择第n个数的两种情况
	for(int i=1;i<=m+n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	} 
	tmp=m;//剩余a的个数
	for(int i=1;i<=n+m;i++){
		//假设这一位放a
		index=C[n+m-i][tmp-1];//在剩下的位置中挑选存放剩余的a
		if(tmp>0&&k<=index){
			cout<<"a";
			tmp--;
		} 
		else{
			cout<<"b";
			k-=index;
		}
	} 
	return 0;
}