「Bzoj 4542」「HNOI2016」大数 (莫队 + 前缀和技巧)

发表于 | 分类于 | | + s

BZOJ 4542
题意：给定一个数字串，询问一些区间组成的数(可含前导零)是否是给定$p​$的倍数。

显然前缀和取余来做。然后刚开始我是想莫队+map，即存前缀和，用公式算出个数，但是这非常麻烦。。
我们可以发现前缀和取余以后，前缀和余数相同，则之间的区间和是模数的倍数
那么我们直接维护前缀和序列的相同数对个数即可，莫队裸题。。
具体证明我们可以设$\text{sum}(i)$为后缀和($[i,n]$表示数)，那么数字即为$\frac{\text{sum}(i) - \text{sum}(j+1)}{10^{n-i}}$
设$[l,r]$表示的数为$\text{num}(l,r)≡\frac{\text{sum}(l)-\text{sum}(r+1)}{10^{r-l+1}}\pmod p$
区间能够被$p$整除当且仅当$\frac{\text{sum}(i) - \text{sum}(j+1)}{10^{n-i}} \equiv \text{num}(l,r)\pmod p $
即$\text{sum}(i) - \text{sum}(j+1) \equiv \text{num}(l,r) \cdot 10^{n-i}\pmod p $

显然$10^{n-i}$与$p$互质，那么这个当$\text{sum}(i)=\text{sum}(j+1)$时，可以确定他们同余

满足条件是$\gcd(p, 10)=1$，所以要特判$p=2,p=5$的情况，具体可以看代码的方法。

注意$r+1$取值为0，要把0加入离散化

知识点
1、前缀和余数相同，则之间的区间和是模数的倍数

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 100000 + 5;

    LL p, n, m, blolen, bl[MAXN], s[MAXN], ls[MAXN], nl, nr, nans, ans[MAXN], pre[MAXN], qwq[MAXN];
    char ch[MAXN];

    struct qry {
        LL l, r, id;
        bool operator < (const qry &rhs) const {
            return bl[l] == bl[rhs.l] ? r < rhs.r : bl[l] < bl[rhs.l];
        }
    } xw[MAXN];

    LL tax[MAXN];
    void update(int x, int v) {
        nans -= tax[s[x]] * (tax[s[x]] - 1) / 2;
        tax[s[x]] += v;
        nans += tax[s[x]] * (tax[s[x]] - 1) / 2;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> p;
        scanf("%s", ch + 1);
        n = strlen(ch + 1);
        blolen = (LL)sqrt(n);
        for (LL i = 1; i <= n; ++i) bl[i] = (i - 1) / blolen + 1;
        LL tmp = 1;
        for (LL i = n; i >= 1; --i) {
            s[i] = (s[i + 1] + tmp * (ch[i] - '0') % p) % p, ls[i] = s[i];
            tmp = (tmp * 10) % p;
        }
        ls[n + 1] = 0;
        sort(ls + 1, ls + 1 + n + 1);
        tmp = unique(ls + 1, ls + 1 + n + 1) - ls - 1;
        for (LL i = 1; i <= n + 1; ++i) s[i] = lower_bound(ls + 1, ls + 1 + tmp, s[i]) - ls;

        cin >> m;
        for (LL i = 1; i <= m; ++i) scanf("%lld%lld", &xw[i].l, &xw[i].r), xw[i].id = i;

        if (p == 2 || p == 5) {
            for (LL i = 1; i <= n; ++i) {
                pre[i] = pre[i - 1], qwq[i] = qwq[i - 1];
                if ((ch[i] - '0') % p == 0) pre[i] += i, qwq[i]++;
            }
            for (LL i = 1; i <= m; ++i) 
                printf("%lld\n", pre[xw[i].r] - pre[xw[i].l - 1] - (qwq[xw[i].r] - qwq[xw[i].l - 1]) * (xw[i].l - 1));
            return 0;
        }

        for (LL i = 1; i <= m; ++i) ++xw[i].r;
        sort(xw + 1, xw + 1 + m);
        nl = 1, nr = 0, nans = 0;
        for (LL i = 1; i <= m; ++i) {
            while (nl > xw[i].l) update(nl - 1, 1), --nl;
            while (nr < xw[i].r) update(nr + 1, 1), ++nr;
            while (nl < xw[i].l) update(nl, -1), ++nl;
            while (nr > xw[i].r) update(nr, -1), --nr;
            ans[xw[i].id] = nans;
        }

        for (LL i = 1; i <= m; ++i) printf("%lld\n", ans[i]);

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------