随机序列求逆(Random Sequence Inverse)

题目描述

对一个正整数 $s$ 反复执行以下过程 $n$ 次，会得到一个二进制字符串：

s = floor((a*s+c)/k) mod m
if (s < floor(m/2))
    output 0
else
    output 1

其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

给定一个二进制字符串 $p$，请问一开始 $s$ 有多少种不同的取值，可以让输出的字符串恰好等于 $p$？

（规定 $s$ 的取值范围：$0 \leq s < m$）

输入格式

第一行：五个整数 $a$，$c$，$k$，$m$，$n$。 第二行：$n$ 个字符，表示给定的二进制字符串 $p$。

输出格式

单个整数：表示满足条件的 $s$ 的初值的方案数。

样例输入 #1

7 3 10 10 10
0000000000

样例输出 #1

7

数据范围

• 对于 50% 的数据：$m \leq 10^4$，$n \leq 10^4$
• 对于 100% 的数据：$1 \leq n \leq 10^5$，$1 \leq m \leq 10^6$
• $0 \leq a < m$，$0 \leq c < m$，$1 \leq k \leq m$

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布