题解 P3413 【SAC#1 - 萌数】

L2_sheep · 2018-09-19 14:25:14 · 题解

这题还可以用数学方法来做。直接求萌数很难，但是求非萌数比较简单，每一位都不和前两位相等就是非萌的。记f(n)是n位的非萌数的总数，可得f(1)=9, f(n)=9×9×8^(n-2)(n>=2)。 接下来，从最高位开始，通过乘法原理和加法原理，就可以求得结果，注意细节。 下面是代码：

#include <stdio.h>
#include <string.h>
#define M 1000000007
#define N 1005
typedef long long LL;

char l[N], r[N];
LL p[N], f[N];

LL solve(char *a, int len)
{
    if(!len) return 0;
    LL sum = 0, tot = 0;
    int i, j, k;
    for(i = 1; i <= len; i++) sum += f[i];
    sum += p[len - 1] * 9 * (a[0] - 49);
    for(i = 1, j = len - 1; i < len; i++, j--){
        k = (a[i] - 1 >= a[i - 1]) + (i > 1 && a[i] - 1 >= a[i - 2]);
        sum += p[j] * (a[i] - 48 - k);
        if(a[i] == a[i - 1] || i > 1 && a[i] == a[i - 2]) break;
    }
    if(i == len) sum += a[i] - 47 - (a[i] >= a[i - 1]) - (i > 1 && a[i] >= a[i - 2]);
    sum %= M;
    for(i = 0; i <= len; i++){
        tot = (tot * 10 + a[i] - 48) % M;
    }
    return tot < sum ? tot - sum + M : tot - sum;
}

int judge(char *a)
{
    if(strlen(a) == 1) return 0;
    if(a[1] == a[0]) return 1;
    int i;
    for(i = 2; a[i]; i++){
        if(a[i] == a[i - 1] || a[i] == a[i - 2]) return 1;
    } 
    return 0;
}

int main() 
{
    int n, i, t, tt;
    LL ans;

    scanf("%s%s", l, r);
    t = strlen(r), tt = strlen(l);

    p[0] = 1;
    for(i = 1; i <= t; i++){
        p[i] = (p[i - 1] << 3) % M;
    }
    f[0] = 0, f[1] = 9, f[2] = 81;
    for(i = 3; i <= t; i++){
        f[i] = (f[i - 1] << 3) % M;
    }

    ans = solve(r, t - 1) - solve(l, tt - 1) + judge(l);
    if(ans < 0) ans += M;
    if(ans == M) ans = 0;
    printf("%lld\n", ans);

    return 0;
}