专栏文章

题解：P13046 [GCJ 2021 Finals] Divisible Divisions

LLastKismet
P13046题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8ze42
此快照首次捕获于
2025/12/01 22:31
3 个月前
此快照最后确认于
2025/12/01 22:31
3 个月前
查看原文

Sol

存在显然 DP 状态 f(i,0/1)f(i,0/1) 表示考虑前 ii 个点分段，最后一段是不是倍数的方案数。显然可以 O(n2)O(n^2) 转移。
假如 gcd⁡(d,10)=1\gcd(d,10)=1，我们可以开桶前缀和做到 O(n)O(n)，具体的，sr−10r−lsl≡0(modd)⇒10−rsr≡10−lsl(modd)s_r-10^{r-l}s_l\equiv0\pmod d\Rightarrow 10^{-r}s_r\equiv10^{-l}s_l\pmod d。然而当二者不互质时不存在逆元，就死掉了。
然而我们发现 1010 的因数只有 1,2,5,101,2,5,10 四个，我们可以将模数 dd 表示成 2x5ym2^x5^ym 的形式，当 r−l≥max⁡(x,y)r-l\ge\max(x,y) 时，模 2x,5y2^x,5^y 的结果均必然为 00，我们只需要考虑模 mm 的结果即可，我们可以用同样的方法前缀和优化转移这部分，而后面几个暴力转移即可。最后复杂度是 O(TNlog⁡D)O(TN\log D)。

Code

CPP
inline void Main(){
	cin>>s>>d;
	n=s.size();s=' '+s;
	rep(i,1,n)a[i]=s[i]-'0';
	rep(i,1,n)a[i]+=a[i-1]*10%d,a[i]%=d;
	repl(i,0,d)sum[i][0]=sum[i][1]=0;S=0;rep(i,1,n)f[i][0]=f[i][1]=0;
	ll m=d,m2=1,m5=1;
	while(!(m%2))m/=2,m2*=2;
	while(!(m%5))m/=5,m5*=5;
	pw[0]=1;rep(i,1,n)pw[i]=pw[i-1]*10%m;
	rep(i,0,n)exgcd(pw[i],m,iv[i],iv[i+1]),iv[i]=(iv[i]%m+m)%m;
	f[0][1]=1;
	rep(i,1,n){
		ll t=10%d;
		per(j,i-1,max(i-20,0)){
			if((a[i]-a[j]*t%d+d)%d==0)f[i][1]+=f[j][0]+f[j][1];
			else f[i][0]+=f[j][1];
			t*=10,t%=d;
		}
		if(a[i]%m2==0&&a[i]%m5==0)
			f[i][1]+=sum[a[i]*iv[i]%m][0]+sum[a[i]*iv[i]%m][1],
			f[i][0]+=S-sum[a[i]*iv[i]%m][1];
		else f[i][0]+=S;
		if(i-20>=0)S+=f[i-20][1],sum[a[i-20]*iv[i-20]%m][0]+=f[i-20][0],sum[a[i-20]*iv[i-20]%m][1]+=f[i-20][1];
	}
	put(f[n][0]+f[n][1]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...