「HNOI2016」大数

题目描述

给定一个质数$p$和一个数字序列，每次询问一段区间$[l,r]$,

求出该序列区间$[l,r]$内的所有子串，满足该子串所形成的数是$p$的倍数(样例的解释也挺直观的)

基本思路

这题的话，满足莫队的离线查询套路，所以用莫队蛮好写。

我们考虑这样一个思路：

众所周知，判断两个数的倍数关系是通过取模来实现的，所以我们考虑对于每一个位置$\ i\ $，定义一个$s_i$

表示$\overline{a_ia_{i+1}...a_n}$这个后缀模$\ p\ $的值，再把它离散化，这样我们就可以实现单次移动在$O(1)时间内完成$(见下)

inline void upt(int x, int v) {

    //x为传入的s的值，v是当前操作带来的变化值(1则为加上贡献，-1则为减去贡献)

    //tong是计数器，存储当前s的数量

    ans -= tong[x] * (tong[x] - 1) / 2;

    tong[x] += v;

    ans += tong[x] * (tong[x] - 1) / 2;

}

搞定这一步，接下来考虑$s$如何转移：

由于是求后缀，我们考虑从后往前枚举$a_i$，我们推一下式子

\[s_i\equiv\overline{a_ia_{i+1}...a_n}\equiv a_i\times10^{n-i+1}+\overline{a_{i+1}a_{i+2}...a_n}\equiv a_i\times10^{n-i+1}\bmod p+s_{i+1}(\bmod\ p)
\]

所以我们只需要在枚举的时候不断更新$10^{n-i+1}$即可

然后我们就可以发现，如果一个区间$[l,r]$所表示的数$\overline{a_la_{l+1}...a_r}$，它如果是$p$的倍数的话，显然有$s_l=s_{r+1}$

小小的证明：

\[\because\ \overline{a_la_{l+1}...a_r} \equiv 0(\bmod\ p)
\]

\[\therefore\ \overline{a_la_{l+1}...a_r}\times10^{n-r}\equiv0(\bmod\ p)
\]

\[\therefore \overline{a_la_{l+1}...a_n}-\overline{a_{r+1}a_{r+2}...a_n}\equiv0(\bmod\ p)
\]

\[\therefore s_l=s_{r+1}
\]

但是！！！

在上述的证明中第一次推导是不严谨的，因为可能存在$p\mid10$使得原式成立，这就引来了重点的分类讨论

对于$p\nmid10$也就是$p\ne2$且$p\ne5$时，我们可以用上述方法，结合莫队来离线求解。

而对于$p=2$或$p=5$的情况，我们直接写特判：

我们发现，判断一个数是不是$2$或$5$的倍数，只需要看个位数字是否被该数字整除即可。

所以我们考虑对于每一个位置$i$，记录下区间$[1,i]$中的$p$的个数及总贡献：

    if (p == 2) bo[0] = bo[2] = bo[4] = bo[6] = bo[8] = 1;

    if (p == 5) bo[0] = bo[5] = 1;

    for (rg int i = 1; i <= n; ++i) {

        f[i] = f[i - 1] + bo[num[i] ^ 48];//f为区间[1,i]中的p的个数

        g[i] = g[i - 1] + bo[num[i] ^ 48] * i;

        //g为区间[1,i]的总贡献，乘上一个i是因为乘法原理，这个可以自己简单想一想

    }

查询贡献时我们就可以直接在线搞：

    m = read();

    for (rg int l, r, i = 1; i <= m; ++i) {

        l = read(), r = read();

        /*-----想一想为什么-----*/

        printf("%lld\n", g[r] - g[l - 1] - (f[r] - f[l - 1]) * (l - 1));

    }

那么至此这道题就解决了。

细节注意事项

这题应该要开$long\ long$
莫队别写挂了。。。

参考代码

/*--------------------------------

  Code name: HNOI2016 BigNumber

  Author: The Ace Bee

  This code is made by The Ace Bee

--------------------------------*/

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define rg register

#define int long long

const int MAXN = 200010;

inline int read() {

    int s = 0; bool f = false; char c = getchar();

    while (c < '0' || c > '9') f |= (c == '-'), c = getchar();

    while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();

    return f ? -s : s;

}

char num[MAXN]; int bo[10], f[MAXN], g[MAXN];

int p, m, s[MAXN], s1[MAXN], gap, pos[MAXN];

struct Ask{ int l, r, id; }q[MAXN];

inline bool cmp(const Ask& x, const Ask& y)

{ return pos[x.l] == pos[y.l] ? x.r < y.r : x.l < y.l; }

int ans, res[MAXN], cnt[MAXN];

inline void upt(int x, int v) {

    ans -= cnt[x] * (cnt[x] - 1) / 2;

    cnt[x] += v;

    ans += cnt[x] * (cnt[x] - 1) / 2;

}

signed main() {

    p = read();

    scanf("%s", num + 1);

    int n = strlen(num + 1);

    if (p != 2 && p != 5) {

        m = read();

        for (rg int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read() + 1, q[i].id = i;

        gap = sqrt(n * 1.0);

        pos[n + 1] = n / gap + 1;

        for (rg int c = 1, i = n; i >= 1; --i, c = c * 10 % p) {

            s1[i] = s[i] = ((num[i] ^ 48) * c % p + s[i + 1]) % p；

            pos[i] = (i - 1) / gap + 1;

        }

        std :: sort(s1 + 1, s1 + 2 + n);

        int t = std :: unique(s1 + 1, s1 + 2 + n) - s1 - 1;

        for (rg int i = 1; i <= n + 1; ++i)

            s[i] = std :: lower_bound(s1 + 1, s1 + 1 + t, s[i]) - s1;

        std :: sort(q + 1, q + 1 + m, cmp);

        for (rg int l = 1, r = 0, i = 1; i <= m; ++i) {

            while (l < q[i].l) upt(s[l++], -1);

            while (l > q[i].l) upt(s[--l], 1);

            while (r < q[i].r) upt(s[++r], 1);

            while (r > q[i].r) upt(s[r--], -1);

            res[q[i].id] = ans;

        }

        for (rg int i = 1; i <= m; ++i) printf("%lld\n", res[i]);

    } else {

        if (p == 2) bo[0] = bo[2] = bo[4] = bo[6] = bo[8] = 1;

        if (p == 5) bo[0] = bo[5] = 1;

        for (rg int i = 1; i <= n; ++i) {

            f[i] = f[i - 1] + bo[num[i] ^ 48];

            g[i] = g[i - 1] + bo[num[i] ^ 48] * i;

        }

        m = read();

        for (rg int l, r, i = 1; i <= m; ++i) {

            l = read(), r = read();

            printf("%lld\n", g[r] - g[l - 1] - (f[r] - f[l - 1]) * (l - 1));

        }

    }

    return 0;

}

完结撒花$qwq$

巴特西

「HNOI2016」大数

题目描述

基本思路

细节注意事项

参考代码

最新文章

热门文章