题解：P8022 [ONTAK2015] Cięcie

yizhishenjing · 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=0，则：

将等式变形

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

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

逆元数组 cir_d=(10^d)^{-1} \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 修改了一些公式推导的小问题（这次修改求管理通过）