← 返回题目列表

AtCoder · arc172_c

C. 选举

中文机器翻译题面 查看原题

分数: 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 A or B.

输入

输入由标准输入按以下格式给出:

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