Description
某日, 小 Q 得到了一种新的生成 01 串的代码
给定一个整数 Z, 执行 n 次下列语句会得到一个 01 串
- z=[(a*z+c)/k]%m;
- if (z<m/2) return 0;else return 1;
现在小 Q 已经得到了某串 01 串, 小 Q 想知道有多少个可能的不同的最初的 Z 可以生成这个
01 串.
Input
第一行五个整数 a, c, k, m, n.
第二行 n 个连续的 01 数字描述 01 串.
Output
一行一个整数表示答案
- Sample Input
- 3 6 2 9 2 10
- Sample Output
- 4
- Data Constraint
对于 30% 的数据, 1<=n,m<=10^3
对于 60% 的数据, 1<=n<=10^3
对于 100% 的数据, 1<=n<=10^5,1<=m<=10^6,0<=a,c<=m,1<=k<=m
题解
考虑字符串哈希.
设
f[
i][j]
表示 i 为 z 的初始值, 进行
2^j
次变化之后, 得到的字符串的哈希值
设
g[i][j]
表示 i 为 z 的初始值, 进行 2^j 次变化后, 得到的数
这两个都是可以通过倍增得到, 字符串的哈希值可以将两个字符串拼接得到
最后, 枚举 z, 倍增判断是否合法
代码
- #include<cstdio>
- using namespace std;
- const int mo=1000000007;
- int a,c,k,m,n,mx,ans,mi[1000010],f[1000010][17],g[1000010][17];
- char s[100010];
- int main()
- {
- freopen("zero.in","r",stdin);
- freopen("zero.out","w",stdout);
- scanf("%d%d%d%d%d",&a,&c,&k,&m,&n);
- scanf("%s",s+1);
- mi[0]=2; for (int i=1;i<=16;i++) mi[i]=(long long)mi[i-1]*mi[i-1]%mo;
- for (int i=1;i<=n;i++) mx=((long long)mx*2+s[i]-'0')%mo;
- for (int i=0;i<m;i++)
- {
- int z=((long long)a*i+c)/k%m;
- g[i][0]=z,f[i][0]=z<m/2?0:1;
- }
- for (int j=1;j<=16;j++)
- for (int i=0;i<m;i++)
- {
- int z=g[i][j-1];
- f[i][j]=((long long)f[i][j-1]*mi[j-1]+f[z][j-1])%mo;
- g[i][j]=g[z][j-1];
- }
- for (int i=0;i<m;i++)
- {
- int t=i,l=0;
- for (int j=n,u=0;j;j>>=1,u++)
- if (j%2==1)
- {
- l=((long long)l*mi[u]+f[t][u])%mo;
- t=g[t][u];
- }
- if (l==mx) ans++;
- }
- printf("%d",ans);
- return 0;
- }
[哈希][倍增] Jzoj P5856 01 串
来源: http://www.bubuko.com/infodetail-2768153.html