?4542: [Hnoi2016]大数

发布时间：2020-12-14 04:38:38 所属栏目：大数据来源：网络整理

导读：4542: [Hnoi2016]大数链接分析：如果p等于2或者5，可以根据最后一位直接知道是不是p的倍数，所以直接记录一个前缀和即可。如果p不是2或者5，那么一个区间是p的倍数，当且仅当$frac{b[l] - b[r + 1]}{10 ^ {r - l + 1}} = 0 (mod p)$。由于p不是2或

4542: [Hnoi2016]大数

链接

分析：

　　如果p等于2或者5，可以根据最后一位直接知道是不是p的倍数，所以直接记录一个前缀和即可。

　　如果p不是2或者5，那么一个区间是p的倍数，当且仅当$frac{b[l] - b[r + 1]}{10 ^ {r - l + 1}} = 0 (mod p)$。

　　由于p不是2或者5，所以10与p互质，条件转化为$b[r] - b[l] = 0 (mod p)$ ，于是将b离散化后，莫队即可。
代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f;
}

const int N = 100005;
int p;
char s[N];
namespace BF1{
    LL s1[N],s2[N];
    void solve() {
        scanf("%s",s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; ++i) {
            s1[i] = s1[i - 1],s2[i] = s2[i - 1];
            if ((s[i] - ‘0‘) % p == 0) s1[i] ++,s2[i] += i;
        }
        int m = read();
        while (m --) {
            int l = read(),r = read();
            printf("%lldn",s2[r] - s2[l - 1] - 1ll * (l - 1) * (s1[r] - s1[l - 1]));
        }
    }
}
namespace BF2{
    struct Que{ int l,r,bel,id; } Q[N];
    bool operator < (const Que &A,const Que &B) { return A.bel == B.bel ? A.r < B.r : A.bel < B.bel; }
    int a[N],cnt[N];
    LL ans[N],b[N],disc[N];
    void solve() {
        scanf("%s",s + 1);
        int n = strlen(s + 1),B = sqrt(n);
        for (int i = n,pw = 1; i >= 1; --i,pw = 1ll * pw * 10 % p) // 开long long
            disc[i] = b[i] = (1ll * (s[i] - ‘0‘) * pw % p + b[i + 1]) % p;
        disc[n + 1] = 0;
        sort(disc + 1,disc + n + 2);
        int tot = 1;
        for (int i = 2; i <= n + 1; ++i) if (disc[i] != disc[tot]) disc[++tot] = disc[i];
        for (int i = 1; i <= n + 1; ++i) a[i] = lower_bound(disc + 1,disc + tot + 1,b[i]) - disc;
        int m = read();
        for (int i = 1; i <= m; ++i) 
            Q[i].l = read(),Q[i].r = read() + 1,Q[i].bel = (Q[i].l - 1) / B + 1,Q[i].id = i;
        sort(Q + 1,Q + m + 1);
        int L = 1,R = 0; LL now = 0;
        for (int i = 1; i <= m; ++i) {
            while (L > Q[i].l) L --,now += cnt[a[L]],cnt[a[L]] ++;
            while (R < Q[i].r) R ++,now += cnt[a[R]],cnt[a[R]] ++;
            while (L < Q[i].l) cnt[a[L]] --,now -= cnt[a[L]],L ++;
            while (R > Q[i].r) cnt[a[R]] --,now -= cnt[a[R]],R --;
            ans[Q[i].id] = now;
        }
        for (int i = 1; i <= m; ++i) printf("%lldn",ans[i]);        
    }
}
int main() {
    p = read();
    if (p == 2 || p == 5) BF1::solve();
    else BF2::solve();
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!