自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:22:52，当前版本为作者最后更新于2019-08-10 11:16:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\rm{Upd\ on\ 2020.1.21:}$ 为避免误导他人，修改了一个严重的常识性错误以及部分不太通顺的语句。原文章写于 $\rm{2019.8.10}$。

用组合数解这道题目实在是再简单不过了。

前置芝士：组合数

$C_{n}^{m}$：在 $n$ 个数中选出 $m$ 个数的方案总数。（不计顺序）

计算公式是

或者

通常的，$C_{n}^{0}=1$。

例如$\ \ C_{4}^{2}=\frac{3*4}{2*1}=6$。

即从 $4$ 个数中选取 $2$ 个有 $6$ 种取法：

$\{1,2\}\ \{1,3\}\ \{1,4\}\ \{2,3\}\ \{2,4\}\ \{3,4\}$。

计算代码如下：

int c(int m,int n)
{
	if(m==0)return 1;
	int mut=1;
	for(int i=n;i>n-m;i--)mut*=i;
	for(int i=m;i>1;i--)mut/=i;
	return mut;
}

那么组合数与这题到底有什么关系呢？

拿 cgx 举例，设 $ans$ 为比 cgx 小的单词个数，初值为 $0$。

$\large1.$ 首先，cgx 肯定比只有一个字母的单词大，$ans+26,\quad ans=26$。

$\large2.$ 其次，cgx 肯定比只有两个字母的单词大。

只有两个字母的单词个数该怎么算呢？就是在 $26$ 个字母中选 $2$ 个。

$ans+C_{26}^{2},C_{26}^{2}=\frac{26*25}{2*1}=325,\quad ans=26+325=351$。

$\large3.$ 只有三个字母

$3.1.$ 第一位：它比以字母 a-b 为第一位的大（ cgx 第一位为 c，所以要比 c 小）

• 以 a 为第一位，且有三位的单词个数：$C_{25}^{2}=\frac{25*24}{2*1}=300$。

  从比 a 大的剩下 $25$ 个字母中选 $2$ 个字母： $ans+300,\quad ans=351+300=651$。

• 以 b 为第一位，且有三位的个数：$C_{24}^{2}=\frac{24*23}{2*1}=276$。

  从比 $b$ 大的剩下 $24$ 个字母中选 $2$ 个字母：$ans+276,\quad ans=651+276=927$。

$3.2$ 第二位（即第一位已经确定为 $c$）：它比以字母 d-f 为第二位的单词大 （第一位为 c ，所以要比 c 大，第二位为 g，所以要比 g 小）

• 第二位为 d 的个数：$C_{22}^{1}=\frac{22}{1}=22$。

  从比 d 大的剩下 $22$ 个字母中选 $1$ 个字母：$ans+22,\quad ans=927+22=949$。

• 第二位为 e 的个数：$C^{1}_{21}=21,ans+21,\quad ans=949+21=970$。

• 第二位为 f 的个数：$C^{1}_{20}=20,ans+20,\quad ans=970+20=990$。

$3.3$ 第三位（一，二位已经确定）：它比以字母 h-w 为第三位的大，共有 $16$ 个。

$ans+16,\quad ans=990+16=1006$

因为比 cgx 小的单词共有 $1006$ 个，所以 cgx 是第 $1007$ 个。

先判断该单词是否存在，再一位一位地去考虑共有多少比给出单词小的单词，如果用的是字符串，则还需要考虑一下边界问题。

#include<bits/stdc++.h>
using namespace std;
string s;
int ans,n;
int c(int m,int n)//组合数计算 
{
	if(m==0)return 1;
	int mut=1;
	for(int i=n;i>n-m;i--)mut*=i;
	for(int i=m;i>1;i--)mut/=i;
	return mut;
}
int main()
{
	cin>>s,n=s.size();
	for(int i=1;i<n;i++)
		if(s[i]<=s[i-1])cout<<0,exit(0);//判断是否存在
	for(int i=1;i<n;i++)ans+=c(i,26);//计算出位数比它小的单词数
	for(int i=0;i<n;i++)//枚举每一位
		for(char j=(i==0?'a':s[i-1]+1);j<s[i];j++)//注意考虑边界
			ans+=c(n-i-1,'z'-j);//因为字符串下标从0开始，所以是n-i-1而不是n-i
	cout<<++ans;//别忘了最后把自己加上
	return 0;
}