因为$a$与$n$互质，所以对于$0$到$n-1$里每个$i$，$aimod n$的值互不相同。
设匹配成功的起点为$i$，那么可以得到$3m$段$aimod n$的值不能取的禁区，每段都是连续区间。
再枚举$n-m+1$到$n-1$的起点，这些单点也是禁区。
找出所有禁区后，答案就是这些禁区的并的补集，扫描线即可。
时间复杂度$O(mlog m)$。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A,B,P,m,i,v,cnt,r,ans;char w[1000010];
struct E{int x,y;E(){}E(int _x,int _y){x=_x,y=_y;}}e[4000010];
inline bool cmp(const E&a,const E&b){return a.x<b.x;}
inline void add(int a,int b,int c,int d){
if(a)e[++cnt]=E(0,a);
if(b<c)e[++cnt]=E(b,c);
if(d<n)e[++cnt]=E(d,n);
}
int main(){
scanf("%d%d%d%d%d%s",&n,&A,&B,&P,&m,w);
for(i=0;i<m;B=(B+A)%n,i++)if(w[i]=='0')add(0,max(P-B,0),n-B,min(P-B+n,n));
else add(max(P-B,0),n-B,min(P-B+n,n),n);
for(i=n-1,B=n-A;i>n-m;B=(B-A+n)%n,i--)e[++cnt]=E(B,B+1);
e[++cnt]=E(n,n+1);
sort(e+1,e+cnt+1,cmp);
for(i=1;i<=cnt;i++){
if(e[i].x>r)ans+=e[i].x-r;
if(e[i].y>r)r=e[i].y;
}
return printf("%d",ans),0;
}