思路:数学

因为是子序列，所以统计出每个字符出现次数，只有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) 种选择 字符 c 出现 z 次，z >= v ，故对于字符 c 出现 t 次的子序列也有 C(z, t) 次

我们从每个字符的角度来看，所有出现至少 t 次的字符对应的 C(cnt, t) 的和为 sum

• 对于字符 a 出现的合法子序列有 C(x, t) * (sum - C(x, t))
• 对于字符 b 出现的合法子序列有 C(y, t) * (sum - C(z, t))
• 对于字符 c 出现的合法子序列有 C(z, t) * (sum - C(y, t))

可以发现有有重复的统计，在字符 a 的统计中，b 和 c 被包括在内 但是在 b 和 c 统计过程中也包括了 a ，所以我们单独计算每部分的和，每种方案最后被统计了 2 遍，除 2 为最终方案数。

时间复杂度：$O(26n)$

代码

MOD = 10 ** 9 + 7

n = int(input())
s = input()

cnt = [0 for _ in range(26)]

for i in s:
    cnt[ord(i) - ord('a')] += 1


def qmi(a, b):
    ans = 1
    while b > 0:
        if b % 2 == 1:
            ans = ans * a % MOD
        a = a * a % MOD
        b //= 2
    return ans


"""
cha, chb
ma, mb
C(ma, 1) C(mb, 1) C(mc, 1)
C(ma, 1) * (sum - C(ma, 1))
C(mb, 1) * (sum - C(mb, 1))
"""

cnt.sort(reverse=True)
while len(cnt) > 0 and cnt[-1] == 0:
    cnt.pop()

if len(cnt) == 1:
    print(0)
    exit(0)

maxc = cnt[0]
fac = [1 for _ in range(maxc + 1)]
ifac = [1 for _ in range(maxc + 1)]
for i in range(2, maxc + 1):
    fac[i] = fac[i - 1] * i % MOD

ifac[maxc] = qmi(fac[maxc], MOD - 2)
for i in range(maxc - 1, 0, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % MOD


def C(a, b):
    return fac[a] * ifac[b] % MOD * ifac[a - b] % MOD


sec = cnt[1]
ans = 0
for i in range(1, sec + 1):
    s = 0
    for j in cnt:
        if j >= i:
            s = (s + C(j, i)) % MOD

    res = 0
    for j in cnt:
        if j >= i:
            t = (s - C(j, i) + MOD) % MOD
            res = (res + t * (s - t) % MOD) % MOD

    res = res * ifac[2] % MOD
    ans = (ans + res) % MOD

print(ans)

题目描述

小美定义一个字符串是平衡串，当且仅当该字符串仅包含两种字符，且两种字符出现的次数相等。例如"ababba"是平衡串。 现在小美拿到了一个仅由小写字母组成的字符串，她想知道该字符串有多少子序列是平衡串？ 定义子序列为从左到右取若干个字符（可以不连续）组成的字符串。例如，"aca"是"arcaea"的子序列。

输入描述

第一行输入一个正整数$n$，代表字符串长度。 第二行输入一个长度为$n$的、仅由小写字母组成的字符串。 $1\leq n \leq 200000$

输出描述

输出一个整数表示答案，由于答案可能很大，请输出答案对 $10^9 +7$ 取模的结果。

样例

输入

5
ababc

输出

9

说明

长度为 2 的子序列，共有 8 个。
长度为 4 的子序列，共有 1 个。