分数: 600 点
问题陈述
今年的AtCoder市长选举有两名候选人,A和B, N 选民已投票。选民被分配的号码来自 1 to N和选民 i (1 \leq i \leq N) 投票给候选人 c_i.
现在,将计票。每张选票计算完毕后,临时结果将公布为以下三种结果之一:
- 结果 A: 目前,候选人A拥有更多票数。
- 结果B: 目前,候选人 B 拥有更多票数。
- 结果 C: 目前,候选人A和B的票数相同。
计票顺序有一个规则:除选民外的所有选民投票 1 必须按选民人数升序计算。 (选民投票 1 可以随时计算。)
可以公布多少种不同的临时结果序列?
什么是临时结果序列?
让 s_i 是结果 (A, B,或 C)报告时 i第投票 (1 \leq i \leq N) 被计数。临时结果的顺序指的是字符串 s_1 s_2 \dots s_N.约束
- N 是一个整数,使得 2 \leq N \leq 1000000.
- 每个 c_1, c_2, \dots, c_N is
AorB.
输入
输入由标准输入按以下格式给出:
N c_1 c_2 \cdots c_N
输出
打印答案。
示例输入 1
4 AABB
示例输出 1
3
在此示例输入中,有四种可能的计票顺序:
- 票数按投票者顺序计算 1 \to 2 \to 3 \to 4.
- 票数按投票者顺序计算 2 \to 1 \to 3 \to 4.
- 票数按投票者顺序计算 2 \to 3 \to 1 \to 4.
- 票数按投票者顺序计算 2 \to 3 \to 4 \to 1.
这些初步结果的序列将是 AAAC, AAAC, ACAC, ACBC 从上到下,因此初步结果有三种可能的顺序。
示例输入 2
4 AAAA
示例输出 2
1
无论计数顺序如何,初步结果的顺序都是 AAAA.
示例输入 3
10 BBBAAABBAA
示例输出 3
5
示例输入 4
172 AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB
示例输出 4
24