TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6561
  • 题目
  • P6561[CF Educational Round 81]Infinite Prefixes
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    一个长度为$n$字符串$s$,其中只包含字符0和1。将字符串$s$复制无数遍拼在一起,得到字符串$t$,即$t=sss\dots$。例如,如果$s=\texttt{10010}$,则$t=\texttt{100101001010010}\dots$。

    一个01字符串的“平衡度”定义为其中字符0的数量减去字符1的数量。对于01字符串$t$,计算它有多少个前缀的平衡度等于$x$。特别的,空字符串也是$t$的一个前缀,它的平衡度为$0$。

    输入格式

    第一行一个整数$T(1\leq T\leq 100)$,共有$T$组测试数据。接下来$2T$行,每两行表示一组测试数据。

    每组数据的第一行包含两个整数$n(1\leq n\leq 10^5)$和$x(-10^9\leq x\leq 10^9)$,表示字符串的长度和平衡度数值。第二行有一个长度为$n$的01字符串$s$。

    输入数据保证$\sum n\leq 10^5$。

    输出格式

    每组数据输出一个整数答案。如果答案为无穷大则输出$-1$。

    样例输入

    4
    6 10
    010010
    5 3
    10101
    1 0
    0
    2 0
    01

    样例输出

    3
    0
    1
    -1


    来源  CF1295B,nodgd搬运