【题解】LOJ 2053 「HNOI2016」大数

请注意,本文编写于 136 天前,最后修改于 136 天前,其中某些信息可能已经过时。

Problem

给定一个长度为 $n$ 的数,和一个素数 $p$
每次询问 $[l,r]$ 中有多少子串是 $p$ 的倍数

Thought

首先肯定是个莫队题

瞎搞的做法

向前面的转移

对于任意一个满足条件的串,其后面不管加上啥都是 $p$ 的倍数,所以可以考虑枚举开头,然后可以算出每一个点作为起始点,结尾点在哪些些范围内可以使得其串为 $p​$ 的倍数

可以使用二分实现,时间复杂度 $O(n\log n)$

向后面的转移

因为前面打上了个标记,我们只需要维护这个点在哪些点的标记之后即可,可以看做是一个前缀和

可以使用主席树维护,时间复杂度 $O(n \log n)$

每次向前转移复杂度 $O(1)$ ,向后转移 $O(\log n)$

总时间复杂度 $O(n\log n+n\sqrt m\log n)$

比较正经的做法

先预处理出 $[x,n]$ 这个串 $\bmod p$ 的值,然后离散化一下,设为 $num[x]$
每次判断一个串 $[l,r]$ 是否是 $p$ 的倍数只需要算出 $\frac{num[l]-num[r+1]}{10^{n-r}}$ 是否是 $p$ 的倍数即可,也就是说答案是否为 $0$

在 $p\neq 2,5$ 时,显然下面那一坨东西对答案没有影响,只需要判断 $num[l]?num[r+1]$ 即可

那么搞个桶瞎存下就可以了

在 $p=2 or 5$ 时,非常好判断,看一下末位即可

每次转移 $O(1)$ ,总时间复杂度 $O(n\sqrt m)$

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
typedef long long ll;
const int N = 100010;
char s[N];
int n, m, sqr;
int L, R;
ll p;
ll num[N], bin[N], tmp[N];
ll ans[N], ANS;
ll key[N];
ll cnt;
struct Query {
    int l, r, id;
    bool operator < (const Query a) const {
        if((l / sqr) == (a.l / sqr))
            return r < a.r;
        return l < a.l;
    }
}q[N];
ll qpow(ll a, ll b, ll p) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = a * ans % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
void add(int pos) {
    ANS += key[num[pos]];
    ++ key[num[pos]];
}
void red(int pos) {
    -- key[num[pos]];
    ANS -= key[num[pos]];
}
void init() {
    p = read();
    scanf("%s", s + 1);
    n = strlen(s + 1);
    sqr = sqrt(n);
    m = read();
}
void work1() {
    for(int i = 1; i <= m; ++ i) {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    L = 1; R = 0;
    int cnt = 0;
    for(int i = 1; i <= m; ++ i) {
        while(L > q[i].l) {
            int pos = -- L;
            if((s[pos] - '0') % p == 0)
                ++ cnt;
            ANS += cnt;
        }
        while(R < q[i].r) {
            int pos = ++ R;
            if((s[pos] - '0') % p == 0) {
                ++ cnt;
                ANS += (pos - L + 1);
            }
        }
        while(L < q[i].l) {
            int pos = L ++;
            ANS -= cnt;
            if((s[pos] - '0') % p == 0)
                -- cnt;
        }
        while(R > q[i].r) {
            int pos = R --;
            if((s[pos] - '0') % p == 0) {
                -- cnt;
                ANS -= (pos - L + 1);
            }
        }
        ans[q[i].id] = ANS;
    }
    for(int i = 1; i <= m; ++ i)
        printf("%lld\n", ans[i]);
}
void work2() {
    bin[0] = 1;
    for(int i = 1; i <= n; ++ i) 
        bin[i] = bin[i - 1] * 10 % p;
    for(int i = n; i ; -- i) {
        num[i] = (bin[n - i] * (s[i] - '0') + num[i + 1]) % p;
        tmp[i] = num[i];
    }
    sort(tmp + 1, tmp + n + 2);
    int cnt = unique(tmp + 1, tmp + n + 2) - tmp - 1;
    for(int i = 1; i <= n + 1; ++ i)
        num[i] = lower_bound(tmp + 1, tmp + cnt + 2, num[i]) - tmp;
    for(int i = 1; i <= m; ++ i) {
        q[i].l = read();
        q[i].r = read() + 1;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    L = 1; R = 0;
    for(int i = 1; i <= m; ++ i) {
        while(L > q[i].l) add(-- L);
        while(R < q[i].r) add(++ R);
        while(L < q[i].l) red(L ++);
        while(R > q[i].r) red(R --);
        ans[q[i].id] = ANS;
    }
    for(int i = 1; i <= m; ++ i)
        printf("%lld\n", ans[i]);
}
int main() {
    init();
    if(p == 2 || p == 5) work1();
    else work2();
    return 0;
}
Comments

添加新评论