配点: 7 点
問題文
文字 'R','G','B' 仅由 组成,长度为 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. S,T 。
对于
S 可以得到第 i 第一个字母
想想是否可以 s_i 、T 可以得到第 j 第一个字母
想想是否可以 t_j 。
N\times N 的格子,并按照以下规则给格子上色。
此处,将字符 'R','G','B' 分别对应为红色、绿色、蓝色。
- s_i=t_j 时,从上到下 i 行,从左数 j 为列中的单元格着色 通过用 s_i 上色。
- s_i\neq t_j 时,从上到下 i 行,从左数 j 将列中的方格涂成红色、绿色、蓝色中与 s_i 托莫 t_j 不同的颜色。
这个方格中从左上到右下的斜列共有 2N-1 条。 请找出颜色单一的列有多少条。
更严格地说,如下所示。 请找出满足以下条件的整数 k\ (-N<k<N) 有多少个。
- 某种颜色 c 存在, 由1\leq i\leq N 和 1\leq i+k\leq N 在任意成立的 i 关于质量 (i,i+k) 的颜色 c 上被涂上。
制約
- 1 \leq N \leq 10^6
- S,T 是一个字符
'R','G','B'仅由
小课题·得点
这个问题可以分解为若干小课题,如果所有小课题的测试用例都正确,则被视为“完成了此小课题”。
提交的源码得分为已正确回答的小课题分数之和。
每个小任务在满足上述约束之外,还需满足以下约束。
- (2 点): N\leq2000
- (5 分数):没有额外约束。
入力
输入是按以下格式从标准输入给出的。
N S T
出力
请输出所有格子都被涂成同一种颜色的斜列的数量。
入力例 1
5 RGBGB GRGRB
出力例 1
6
k=-4,-3,-1,2,3,4 可以得到第 6 满足条件。
例如,k=-3 条件得以满足,是因为格子 (4,1),(5,2) 两者都是绿色涂色所验证的。
入力例 2
3 RRR BBB
出力例 2
5
入力例 3
10 BGGGRBBGRG RGBBRGRGGG
出力例 3
4