【HNOI2016】大数

傷城~ 2021-12-20 10:15 242阅读 0赞

## 【HNOI2016】大数 ##

[题目链接][Link 1]

##### 题目描述 #####

小 B 有一个很大的数 $ S $，长度达到了 $ N $ 位；这个数可以看成是一个串，它可能有前导 $ 0 $，例如 `00009312345` 。小 B 还有一个素数 $ P $。

现在，小 B 提出了 $ M $ 个询问，每个询问求 $ S $ 的一个子串中有多少子串是 $ P $ 的倍数（$ 0 $ 也是 $ P $ 的倍数）。例如 $ S $ 为 `0077` 时，其子串 `007` 有六个子串：`0`, `0`, `7`, `00`, `07`, `007`；显然 `0077` 的子串 `077` 的六个子串都是素数 $ 7 $ 的倍数。

##### 输入格式 #####

第一行一个整数：$ P $。

第二行一个串：$ S $。

第三行一个整数：$ M $。

接下来 $ M $ 行，每行两个整数 $ \\text\{fr\}, \\text\{to\}$，表示对 $ S $ 的子串 \$S\[\\text\{fr\} \\ldots \\text \{to\}\]\$ 的一次询问。

注意：$ S $ 的最左端的数字的位置序号为 $ 1 $；例如 $ S $ 为 $ 213567 $，则 $ S\[1\] $ 为 $ 2 \$，\$ S\[1 \\cdots 3\] $为 $ 213 $。

##### 输出格式 #####

输出 $ M $ 行，每行一个整数，第 $ i $ 行是第 $ i $ 个询问的答案。

##### 样例 #####

#### 样例输入 ####

11 121121 3 1 6 1 5 1 4

#### 样例输出 ####

5 3 2

#### 样例解释 ####

第一个询问问的是整个串，满足条件的子串分别有：`121121`、`2112`、`11`、`121`、`121`。

##### 数据范围与提示 #####

对于所有的数据，$ N,M \\leq 100000 \$，\$ P $ 为素数。

[参考题解][Link 2]

我们要求的是  
\\\[ \\displaystyle \\begin\{align\} ans&=\\sum\_\{i=l\}^r\\sum\_\{j=i\}^r \[\\sum\_\{k=i\}^js\_k\\cdot 10^\{j-k\} ==0\\ mod\\ p\]\\\\ &=\\sum\_\{i=l\}^r\\sum\_\{j=i\}^r10^\{j\}\[\\sum\_\{k=i\}^js\_k\\cdot 10^\{-k\} ==0\\ mod\\ p\] \\end\{align\} \\\]  
如果质数\$P\$不等于\$2\$或\$5\$，那么\$10^j\$不可能等于\$0\$，并且\$10^k\$是有逆元的。

我们设\$s\_k\\cdot 10^\{-k\}\$的前缀和为\$sum\_k\$，则我们要求的就是：  
\\\[ \\displaystyle \\sum\_\{i=l\}^r\\sum\_\{j=i\}^r\[sum\_j==sum\_i\] \\\]  
这就是一个经典的莫队问题。

类似的题还有【CQOI2018】 异或序列。

当\$P\$等于\$2\$或者\$5\$的时候，我们知道只需要判断一个字串的最后一位就可以了，所以很好做。

代码：

#include<bits/stdc++.h>
    #define ll long long
    #define N 200005
    
    using namespace std;
    inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    ll p;
    char s[N];
    int n,m;
    int bel[N];
    ll ans[N];
    ll sum[N],d[N];
    ll cnt[N];
    const int blk=450;
    struct query {
        int l,r;
        int id;
        bool operator <(const query &a)const {
            if(bel[l]!=bel[a.l]) return l<a.l;
            return bel[l]&1?r<a.r:r>a.r;
        }
    }q[N];
    
    ll ksm(ll t,ll x,ll mod) {
        ll ans=1;
        for(;x;x>>=1,t=t*t%mod)
            if(x&1) ans=ans*t%mod;
        return ans;
    }
    
    ll now=0;
    void add(int v) {
        now+=cnt[sum[v]];
        cnt[sum[v]]++;
    }
    
    void del(int v) {
        cnt[sum[v]]--;
        now-=cnt[sum[v]];
    }
    
    ll tot[N],size[N];
    int main() {
        p=Get();
        scanf("%s",s+1);
        n=strlen(s+1);
        m=Get();
        for(int i=1;i<=m;i++) {
            q[i].l=Get()-1,q[i].r=Get();
            q[i].id=i;
        }
        
        if(p!=2&&p!=5) {
            for(int i=0;i<=n;i++) bel[i]=i/blk+1;
            sort(q+1,q+1+m);
            d[++d[0]]=0;
            ll inv10=ksm(10,p-2,p),t=inv10;
            for(int i=1;i<=n;i++) {
                sum[i]=(sum[i-1]+(s[i]-'0')*t)%p;
                t=t*inv10%p;
                d[++d[0]]=sum[i];
            }
            sort(d+1,d+1+d[0]);
            int cc=unique(d+1,d+1+d[0])-d-1;
            for(int i=0;i<=n;i++) sum[i]=lower_bound(d+1,d+1+cc,sum[i])-d;
            
            int l=0,r=-1;
            for(int i=1;i<=m;i++) {
                while(r<q[i].r) add(++r);
                while(l>q[i].l) add(--l);
                while(r>q[i].r) del(r--);
                while(l<q[i].l) del(l++);
                ans[q[i].id]=now;
            }
            for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
        } else {
            if(p==2) {
                for(int i=1;i<=n;i++) {
                    tot[i]=tot[i-1];
                    size[i]=size[i-1];
                    if((s[i]-'0')%2==0) {
                        tot[i]+=i;
                        size[i]++;
                    }
                }
            } else {
                for(int i=1;i<=n;i++) {
                    tot[i]=tot[i-1];
                    size[i]=size[i-1];
                    if((s[i]-'0')%5==0) {
                        tot[i]+=i;
                        size[i]++;
                    }
                }
            }
            for(int i=1;i<=m;i++) {
                cout<<(tot[q[i].r]-tot[q[i].l])-(size[q[i].r]-size[q[i].l])*q[i].l<<"\n";
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10481091.html

[Link 1]: https://loj.ac/problem/2053
[Link 2]: https://blog.csdn.net/lzxzxx/article/details/51197592