洛谷：P1246：编码

题目

先看长度为1的单词，这个很简单：a-z，一共26个。

长度为2呢？

原则上是从26个字母中选两个排列，但是由于这两个字母排列的一定会出现一个的“错误次序”（也就是大的字母在前、小的字母在后），所以要除以2，也就变成只考虑组合的情况。所以，长度为2的单词只有\(C_{26}^2=325\)个。

也就是说：

长度n	有几个	加上前面长度为小于n的单词数量	序号
1	26	26	1-26
2	325	351	27-351

以dhz为例，

第一个字母是d，它之前还有a|b|c开头的三字母单词，所以要计算三个首字母的组合之和：
1. a开头：后面两个字符只有在25个选择中选2个，所以是\(C_{25}^2=300\)；
2. b开头：后面两个字符只有在24个选择中选2个，所以是\(C_{24}^2=276\)；
3. c开头：后面两个字符只有在23个选择中选2个，所以是\(C_{23}^2=253\)；
4. 总数是：\(300+276+253=829\)个。
第二个字母是h，由于第一个用了d，所以之前只能是e开始到g结束。
1. e：后面一个字符只有在\(26-(a-e的字母数=5)=21\)个选择中选1个，所以是\(C_{21}^1=21\)；
2. f：后面一个字符只有在\(26-(a-f的字母数=6)=20\)个选择中选1个，所以是\(C_{20}^1=20\)；
3. g：后面一个字符只有在\(26-(a-g的字母数=7)=19\)个选择中选1个，所以是\(C_{19}^1=19\)；
4. 总数是：\(21+20+19=60\)个。
第三个字母是z，由于第二个用到了h，所以只能是从i开始到y结束。一共是17个。可以同样参考上述步骤，用组合求出。注意：此时其实已经没有组合的可能和必要了，因为这么多字符里你只能选一个。

以上数字加起来：\(351（长度为1和2）+829+60+17=1257\)，也就是说dhz之前有1257个，那么dhz自然就是第1258个。

所以，用循环来完成这个过程的时候，需要不断计算组合的累加值。而计算每个组合的关键，是框定有多少可选项（n）以及要选几个（k），才能计算出\(C_n^k\)。

这样我们就确定了计算组合的两个值。

\(C_n^k\)的计算公式很简单，但用到大量的阶乘，比较耗时。我们可以进行化简。

观察公式：\(C_n^k=\frac{n!}{k!(n-k)!}\)，可以看到\(\frac{n!}{(n-k)!}\)可以大量约简。它就等于\((n-k+1)\times(n-k+2)\times...\times n\)，正好有k项。因此都只要计算k次即可。²

  for (int i = n; i > n - m; i--) {
    result *= i;
  }
  for (int i = m; i > 1; i--) {
    result /= i;
  }

Solution

这题的核心，是通过简单例子的分析，找到加和，以及分段数量等于组合。