问题 4852 --1.古老谜题

4852: 1.古老谜题

题目描述

  给定一个长度为 $n$ 的 $01$ 序列 $a_1\sim a_n$。
请你求出有多少个整数三元组 $(l,r,p)$,使得 $1 \leq l < r \leq n$ 并且 $a_p=1$,且 $[l,p]$ 和 $[p,r]$ 中 $1$ 的个数相同。

输入

第一行为一个正整数 $\mathrm{idx}$ 表示该测试点所属的子任务编号,子任务的详细信息请见「数据范围」。样例的子任务编号为 0。
第一行为一个正整数 $n$。
第二行为一个长度为 $n$ 的字符串,仅包含 0 和 1。

输出

输出仅一行表示答案。

样例输入输出

输入#1 复制
7
1101011
输出#1 复制
7
输入#2 复制
1990
1111110111111101111101111111111111100111111110111111111111110111111011111111110011111111111011111110111001111111111110111111101111111011111111111111110111111110110111111111111111111111011101111101111111010111111111111111111011111101111011110111111111101101111111111001111111111111111101111101101111111011111111100001110110111111111111111001011111111111111111111110111111111111111111011101101111011111111010111101101111011111111111111111110111111101011111101111110111111101111111111111101101111110111111111111111111111101110111011101111101111111111111110101111111111111111101111111111111111111111110111110111111111111011111111111111111110110111111101111111111111111011101111111111111111010011101110101101101100110001010111110001101100101100010111000011100011010000111101111110101111010111111101001101100011101111010000101101111111011110110011110101110111110011111100011101111101101100110001110001011111111011000101011000111011011110111011010111011110011010111110100010111010101111100110011010110101111111110110111111011010010110110100111011110111101011101111111101001100011011110001101001011111100111111101111111110111010010111110100000111110110001101111111101111011001110111101101011101111001011111011001111111111111001010011110111111111111101111101010111110100111011011101111100010111111111111100111001100111111010111011101101110110010001110100111110001101111111010101011111111111011111101101101101101111011101111111001111001101101011111111111111001001110000111111110101111111011010101111100111111110000011111010111111010010111111001101001000011111010011110001110111110001110011111111011100100100101110111001011101111110000000101111110101111101111111111001101011111010110101111111110101011111111011111111111011011111011111001111011011111100110110111011111111011111011110111111011110101001110101111010011101111111001011110011111100111111110001011110111110010110110010000001111011000001101011100101110111110011111011111110111100100101110111110010111101111101000011100001011111011011011010110
输出#2 复制
988067

提示

本题采用捆绑测试,只有通过一个子任务中的全部测试点才能拿到这个子任务的分数。

子任务 1(8 分):$n \leq 50$;
子任务 2(26 分):$n \leq 300$。
子任务 3(14分):$n \leq 2000$。
子任务 4( 10分):字符串中有且仅有 3 个1 。
子任务 5( 12分):字符串中全是 1。
子任务 6(25 分):无特殊限制。
对于所有数据,$1 \leq n \leq 10^6$。

序号 标题 作者 发表时间 费用 订购数 操作