小易的字典

思路：
a..a z..z n个a和m个z, 设C(n,m)表示总的排列个数
那么C(n,m)有两种情况 y以a为开头的和以z为开头的
我们可以得到递推式   C(n, m) = C(n-1, m) + C(n,m-1)
C(0,0) = 0,  C(n,0) = 1, C(0,m)=1
可以算出矩阵C
因为是按照字典排序，所以a在前，z在后
我们考虑第k个字符串的首位，C(n-1,m)位之前都是a,之后都是z
只要k和C(n-1,m)比较就可以知道首位了，
去掉第一位后，我们可以得到剩下n+m-1字符串的位置，重复前面的过程

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int n,m,k;
        n = cin.nextInt();
        m = cin.nextInt();
        k = cin.nextInt();

        BigInteger[][] c = new BigInteger[n+1][m+1];
        for(int i=0;i<=n;i++){
            c[i][0] = BigInteger.ONE;
        }
        for(int i=0;i<=m;i++){
            c[0][i] = BigInteger.ONE;
        }
        c[0][0]=BigInteger.ZERO;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                c[i][j] = c[i-1][j].add(c[i][j-1]);
            }
        }
        if(BigInteger.valueOf(k).compareTo(c[n][m])>0){
            System.out.println("-1");
            return;
        }
        int cn, cm,ck;
        cn = n;
        cm = m;
        ck = k;
        StringBuilder sb = new StringBuilder(n+m);
        for(int i=0;i< n+m; i++){
            BigInteger t = c[cn-1][cm];
//            if(ck <=t) {
            if(BigInteger.valueOf(ck).compareTo(t)<=0) {
                sb.append("a");
                cn--;
            }else{
                sb.append("z");
                ck-=t.longValue();
                cm--;
            }
            if(cn==0){
                for (int j = 0; j < cm; j++) {
                    sb.append("z");
                }
                break;
            }
            if(cm==0){
                for (int j = 0; j < cn; j++) {
                    sb.append("a");
                }
                break;
            }
        }
        System.out.println(sb.toString());
    }
}

顶我上去，全场最好理解

1.n个'z'和m个‘a’组成的组合数的关系

dp[i][j]=dp[i-1][j]+dp[i][j-1]

2.关于找第几个的问题，递归

固定右边x位，从m-1个z开始固定，a的个数逐渐增加

刚好没有进入下一层递归，就应该是aaazz..zzaaa这种形式

如果不是k不是刚好减去就应该是aa...aazxxxxx后面就进入xxxx里面再做一层递归

import java.util.*; public class Main { public static void main(String[] args) {
           Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int k=sc.nextInt(); long[][] dp=new long[101][101]; //dp[i][j]i个'a'和j个'b'的组合数 for(int i=0;i<101;i++)
               dp[i][0]=1; for(int j=1;j<101;j++)
               dp[0][j]=1; for(int i=1;i<101;i++) { for(int j=1;j<101;j++) {               
                   dp[i][j]=dp[i-1][j]+dp[i][j-1];                                                      
                 }
           } if(dp[n][m]<k)
           {
               System.out.println("-1"); return;
           }
           Main main=new Main();
           StringBuilder sb=new StringBuilder();
           main.solve(n, m, k, sb, dp);          
    } public void solve(int a,int z,int k,StringBuilder sb,long[][] dp) { if(a==0) { for(int i=0;i<z;i++) sb.append("z");
              System.out.println(sb.toString()); return;
           } if(z==0) { for(int i=0;i<a;i++) sb.append("a");
              System.out.println(sb.toString()); return;
           } int la=0,lz=z-1; while(k-dp[la][lz]>=0)
           {
              k-=dp[la][lz];
              la++;
           } if(k==0)
           { for(int i=0;i<a-la+1;i++) sb.append("a"); for(int i=0;i<z;i++) sb.append("z"); for(int i=0;i<la-1;i++) sb.append("a");
              System.out.println(sb.toString()); return;
           } for(int i=0;i<a-la;i++) sb.append("a");
           sb.append("z");
           solve(la,lz,k,sb,dp);
     }
}