自动搬运

查看原文

来自洛谷，原作者为

	yizhishenjing 深鲸

搬运于2025-08-24 22:35:13，当前版本为作者最后更新于2025-07-22 16:34:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目描述

给定一个长度为 $k$ 的数字串 $N$ 和三个质数 $p$，$q$，$r$，需要将数字串划分为三段非空子串，使得：

• 第一段能被 $p$ 整除。
• 第二段能被 $q$ 整除。
• 第三段能被 $r$ 整除。
• 每一段不含前导零（单独的 $0$ 是允许的）。

解决思路

我们设三段分别为 $[0,i-1]$，$[i,j-1]$，$[j,k-1]$。

由于每一段不能有前导 $0$，因此：

• 第一段：如果长度大于 $1$，则第一个字符不能为 $0$，如果长度为 $1$，可以是 $0$。
• 第二段：如果长度大于 $1$，则 $s_i$ 不能为 $0$。
• 第三段：如果长度大于 $1$，则 $s_j$ 不能为 $0$。

直接枚举 $i$ 和 $j$ 的话，时间复杂度为 $O(k^2)$，肯定会炸掉，因此考虑优化。

首先注意到有前缀和后缀，所以考虑预处理前缀模和后缀模，用 $sump_i$ 表示子串 $s_{0 \ldots i-1}$ 模 $p$ 的值，用 $sumq_i$ 表示子串 $s_{0 \ldots i-1}$ 模 $q$ 的值，用 $hour_i$ 表示子串 $s_{i \ldots k-1}$ 模 $r$ 的值。

然后我们发现 $sumq_i$ 有前缀影响，所以我们需要消除前缀影响，并且需要快速判断是否存在 $j$ 使得满足条件。

$$B \bmod q=(sumq_j-sumq_i \times 10^{j-i}) \bmod q$$

需要 $B \bmod q=0$，则：

$$sumq_j \equiv sumq_i \times10^{j-i} \bmod q$$

将等式变形

$$sumq_i \equiv sumq_j \times (10^{j-i})^{-1} \bmod q $$

其中 $(10^{j-i})^{-1}$ 是 $10^{j-i}$ 在模 $q$ 下的逆元

为了将问题转化为等值问题，可以引入逆元，设 $d=j-i$

逆元数组 $cir_d=(10^d)^{-1} \bmod q$ ，满足：

$$sumq_i \times (10^j)^{-1} \equiv sumq_j \times cir_d \times (10^j)^{-1} $$

定义

$$hash_k=sumq_k \times (10^k)^{-1} \bmod q$$

化简后得：

$$hash_i \equiv hash_j \bmod q$$

这样，我们就可以通过统计 $hash_j$ 的值来快速找到符合条件的 $j$。

关于枚举顺序，考虑枚举第一段结束位置 $i$ 并动态维护 $j$ 的位置，用指针 $last$ 从后向前扫描，将满足合法 $j$ 的 $hash_j$ 丢进数组里，最后再分类讨论一下就做完了。

Ac Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,p,q,r,sump[1992929],sumq[1992929],hour[1992929],zhir[1992929];

int hash1[1992929],pw[1992929],cir[1992929],ans1[1992929];

string s;
int ksm(int a,int b,int mod){//快速幂 
	int res=1;
	while(b){
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod,b>>=1;
	}
	return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>k>>p>>q>>r;
    
    cin>>s;
    //预处理前缀模值 
    for(int i=1;i<=k;i++){
    	
    	sump[i]=((sump[i-1]*10)%p+(s[i-1]-'0'))%p;
    	
    	sumq[i]=((sumq[i-1]*10)%q+(s[i-1]-'0'))%q;
    	
	}
	//预处理后缀模值 
	int base=1;
	
	for(int i=k-1;i>=0;i--){
		
		hour[i]=((s[i]-'0')*base+hour[i+1])%r;
		
		base=(base*10)%r;
		
	}
	//验证第三段的合法性 
	for(int i=0;i<k;i++){//表示从i开始的第三段是否合法 
		
		int len=k-i;//第三段长度 
		
		if(len==1){
			zhir[i]=(hour[i]%r==0);
		}else{
			zhir[i]=((hour[i]%r==0)&&(s[i]!='0'));
		}
		
	}
	
	pw[0]=1;//预处理10的幂 
	for(int i=1;i<=k;i++){
		pw[i]=(pw[i-1]*10)%q;
	}
	//求逆元 
	for(int i=0;i<=k;i++){
		cir[i]=ksm(pw[i],q-2,q);//// 费马小定理求逆元
	}
	
	for(int i=0;i<=k;i++){ 
		hash1[i]=(sumq[i]*cir[i])%q;
	}
	//枚举划分方案 
	int ans=0,last=k-1;
	
	for(int i=k-2;i>=1;i--){//倒序枚举第一段结束位置i（第一段长度i）
		
		if(i>1&&s[0]=='0')continue;
		
		if(sump[i]%p!=0)continue;
		//将满足j>=i+2的合法第三段起始位置j加入ans1 
		while(last>=i+2){
			
			if(zhir[last]){
				
				int H=hash1[last];
				
				while(H<0)H+=q;
				
				H%=q;
				
				ans1[H]++;
			}
			
			last--;
			
		}
		 //情况1:第二段长度为1（j=i+1）
		if(i+1<k){
			
			if(zhir[i+1]){
				
				if(s[i]=='0'){
					
					ans++;
					
				}
			}
		}
		//情况2：第二段长度>1
		if(s[i]!='0'){
			
			int H=hash1[i];
			
			while(H<0)H+=q;
			
			H%=q;
			
			ans+=ans1[H];
			
		}
	}
	cout<<ans;
    return 0;
}

2025-07-29 修改了一些公式推导的小问题（这次修改求管理通过）