#P13991. Heat Abnormal

Heat Abnormal

Heat Abnormal

题目描述

死んだ変数で繰り返す

数え事が孕んだ熱

どこに送るあても無く

あわれな独り事を記している

—— 熱異常

给定两个 0101 序列 S,TS,T,将 SS 视作入栈顺序,TT 视作出栈顺序,你需要求出所有可能第一个出栈的元素。 为了使输出不太多,你只需要输出这些编号的总和。

输入格式

第一行一个正整数 nn。

接下来一行一个长为 nn 的 0101 字符串 SS。

接下来一行一个长为 nn 的 0101 字符串 TT。

输出格式

仅一行一个整数表示所有可能第一个出栈的元素的编号总和,编号从 11 开始。

样例

样例 1

3
100
001
5

样例 2

4
0101
1001
2

样例 3

见附加文件 heat3.in/heat3.out,该组数据满足 Subtask 3 的特殊限制。

样例 4

见附加文件 heat4.in/heat4.out,该组数据满足 Subtask 4 的特殊限制。

样例 5

见附加文件 heat5.in/heat5.out。

数据范围

对于所有数据,满足 1≤n≤5×1061\le n\le 5\times 10^6,S,TS,T 中的 0101 个数相同。

子任务编号 特殊限制 分数
1 n≤3n\le 3 55
2 SS 是全 00 串
3 n≤100n\le 100 1010
4 n≤105n\le 10^5 5050
5 无 3030