hogloidのブログ

へなちょこ

PKU 1850 Code

昔やってみて集中力が持たなくてやめたのをもう一回やってみたら意外とすっきりかけました
使った文字+残りの文字数 で作ることができるすべての文字列の数を求める関数を作ります。
便宜上文字数0のとき1を返します。

int befsize(int n,int usedword){
	if(n==0) return 1;
	int res=1;
	int num=26-usedword;
	for(int i=num;i>num-n;--i)//calc numCn
		res=res*i/(num+1-i);
	return res;
}
int main(){
	string s;cin>>s;
	int res=1;
	int flag=0;
	REPN(i,s.size(),1){
		if(s[i]<=s[i-1]){
			printf("0\n");
			return 0;
		}
	}

	REPN(i,s.size(),1){
		res+=befsize(i,0);
	}
	int befused=-1;
	REP(i,s.size()){
		int used=s[i]-'a';
		REPN(j,used+1,befused+2)
			res+=befsize(s.size()-i-1,j);
		befused=used;
	}
	printf("%d\n",res);

	return 0;
}