因为是子序列,所以统计出每个字符出现次数,只有26种字符。
考虑当前两种字符 a 和 b 分别出现了 x 次和 y 次 ,v = min(x, y) 这两种字符可以构成 a 和 b 均出现相同次数的子序列有: 长度为 2,4,6,8,... ,2v 的这 v 种子序列 ,两种字符分别出现 1,2,3,4,...,v 次
字符 a 和 b 均出现 t 次,对于字符 a 有 C(x, t) 种选择,字符 b 有 C(y, t) 种选择
小蓝得到了一个长度为 n 的字符串 S,仅由小写英文字母组成。他定义一个子序列为“双星子序列”,当且仅当该子序列恰好由两种互不相同的字符构成,且这两种字符的出现次数相等。
例如,子序列 "abab" 由字符 a 和 b 组成,各出现 2 次,因此它是双星子序列。
现在小蓝想知道,字符串 S 有多少个不同的双星子序列?答案可能很大,请你输出答案对 109+7 取模后的结果。
子序列是指从原字符串中按顺序选取若干个字符(可以不连续)得到的字符串。两个子序列只要选取字符的位置集合不同,就视为不同的子序列。
约束条件:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.