题目描述

题解

首先对于求x<p的情况，把0和p都当作终点，然后求出到其中任意一个的期望步数，再考虑上到分别两个的概率（相加为1，所以只用算一个）即可求出

可以简单化一下解一下方程即可

题解做法是从低往高数位dp，考虑当前具体填什么以及之前是否进位

还有一种清真做法，直接求一个前缀1~t的答案和，根据当前位是否为0，不为0的话考虑进位还是变为0，可以枚举具体的数然后考虑范围，也可以直接根据当前t%p进行分类O(1)计算

然后加上记忆化就可以过了

code

卡常带师

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define low(x) ((x)&-(x))
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;

ll s,A,B,L,R,ans,S,f[100001],g[100001],p1[100001],p2[100001];
int p,i,j,k,l,hs[1000008];

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
ll js(register ll t)
{
	int i;
	
	if (t<0) return 0;
	if (t<p) return g[t];
	ll T=t%p,T2=t/p,tt=t%1000007;
	if (hs[tt]) return hs[tt];
	
	if (t>p) hs[tt]=(js(T2)*(1+p2[p-1]-p2[T]+(p1[T]-1))+js(T2-1)*(p1[p-1]-p1[T])+(T2)%mod*(f[p-1]-f[T])+js(T2+1)*p2[T]+(T2+1)%mod*f[T])%mod;
	else
	hs[tt]=(js(T2)*(1+p2[p-1]-p2[T])+js(T2-1)*(p1[p-1]-p1[T])+(T2)%mod*(f[p-1]-f[T]))%mod;
	return hs[tt];
}
void js1(int t,ll k,ll b)
{
	if (t==p) return;
	
	ll S=qpower(1-(1-s)*k%mod,Mod);
	js1(t+1,s*S%mod,(1+b*(1-s)%mod)*S%mod);
	f[t]=(k*f[t+1]+b)%mod;
}
void js2(int t,ll k,ll b)
{
	if (t==p) return;
	
	ll S=qpower(1-(1-s)*k%mod,Mod);
	js2(t+1,s*S%mod,b*(1-s)%mod*S%mod);
	p1[t]=(k*p1[t+1]+b)%mod;
}

int main()
{
	freopen("lowbit.in","r",stdin);
	#ifdef file
	freopen("lowbit.out","w",stdout);
	#endif
	
	scanf("%d%lld%lld%lld%lld",&p,&A,&B,&L,&R);s=A*qpower(B,Mod)%mod;p1[0]=p2[p]=1;
	if (p==2) f[1]=1,p1[1]=1-s,p2[1]=s,g[1]=qpower(1-s,Mod);
	else
	{
		js1(1,s,1),js2(1,s,1-s);
		g[1]=f[1]*qpower(p1[1],Mod)%mod;p2[1]=1-p1[1];
		fo(i,2,p-1) p2[i]=1-p1[i],g[i]=(p2[i]*g[1]+f[i])%mod;
	}
	fo(i,1,p-1) g[i]=(g[i]+g[i-1])%mod,f[i]=(f[i]+f[i-1])%mod,p1[i]=(p1[i]+p1[i-1])%mod,p2[i]=(p2[i]+p2[i-1])%mod;
	printf("%lld\n",((js(R)-js(L-1))%mod+mod)%mod);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6640. 【GDOI20205.20模拟】lowbit

原文：https://www.cnblogs.com/gmh77/p/12967218.html