首页 > 代码库 > 一个字符串排列的小算法
一个字符串排列的小算法
给定n个A和2n个B,用这些字符拼成一个字符串,要求这个串的所有前缀和后缀B的个数始终不少于A。
(一个字符串的前缀是只从开头到某个位置为止的子串,后缀是只从某个位置到结尾的子串)。
输入格式
多组数据,每组数据只有一行,包含一个正整数n。(n<=10^17)。
输出格式
每组数据输出一行,最终结果对99991取余数的结果。
def count(n,m,ac,bc,sb):
if(ac==n or bc==m):
print sb;
return 1;
if(ac==bc):
sb.append(‘b‘)
tmp = count(n,m,ac,bc+1,sb);
sb.pop()
return tmp;
else:
sb.append(‘a‘);
tmp0=count(n,m,ac+1,bc,sb);
sb.pop();
sb.append(‘b‘);
tmp0 = tmp0+count(n,m,ac,bc+1,sb)
sb.pop()
return tmp0;
n=2
m=2*n
print count(n,m,0,0,[]);
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。