Skip to content

14085: 【原4085】calc

题目

题目描述

author: BowenTan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4085 时间限制:2s

Description

给定n,a,b,p(n,a,b,p≤10^9),其中n,a互质

定义一个长度为n的01串c[0..n−1],其中c[i]=0当且仅当(ai+b) mod n < p。

给定一个长为m(m≤10^6)的小01串d,求出这个字符串在大串c中出现了几次。

input format

本题包含多组输入数据,数据开始首先输入数据组数T(T<=8)

每组数据的第一行是四个数n, a, b, p。 第二行是一个01串d。

output format

出现的次数

sample input

1
9 5 6 4 3
101

sample output

3

explanation

limits

  • 对于10%的数据,n<=1,000
  • 对于另外10%的数据,n<=1,000,000
  • 对于100%的数据,n,a,b,p<=1,000,000,000, m<=1,000,000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!