Luogu4349 [CERC2015]Digit Division

发布于 2019-09-17  231 次阅读


题意

有一个N位的数字,将其分割,保证每个区间里的数字可以被M整除。问有多少种方法,将答案对 10^9 + 7 取余

题解

刚开始看到这个题我还以为是个DP,跟那个数字游戏 还有点像的,后来发现不会搞看了一下题解然后开始往数学的方向想。

思路其实还挺简单的。
对于一个数 m ,如果有 m|a & m | b 那么把ab连起来也有 m|(a * \lceil log_{10}b\rceil + b

证明一下(Luogu上神仙的题解都没有证,可能是因为我TCL,还是证一下):

$a, b$拼接以后的数是:$a * \lceil log_{10}b\rceil + b$

p_1, p_2分别为 a 的一对非平凡因子

$∵m|a$

$∴m|p_1 * p_2$

由此可得:$m|p_1 p_2 \lceil log_{10}b\rceil + b$

之后还有一个结论是,这个数可以被划分的方法有:可以划分的位置个数2^{可以划分的位置个数-1}
不证了,组合数学基础

还要注意的就是,最后一个区间如果不能被整除,那么答案应该为0

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int SIZE = 300000 + 5;

int n, m;
char str[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline LL Qpow(LL b, LL p, LL k)
{
    LL ans = 1, t = b;
    for ( ; p; p >>= 1, t = t * t % k)
        if (p & 1) ans = ans * t % k;
    return ans % k;
}

int main()
{
    int cur = 0, cnt = 0;
    n = read(), m = read();
    scanf("%s", str + 1);
    for (int i = 1; i <= n; i++)
    {   
        cur = ((cur << 1) + (cur << 3) + str[i] - '0') % m;
        cnt += (!cur);
    }
    printf("%lld", cur ? 0 : Qpow(2, cnt - 1, 1e9 + 7));
    return 0;
}


朴实沉毅