2013腾讯马拉松初赛 ACM 吉哥系列故事——恨7不成妻

[c]代码库

/*

2013腾讯马拉松初赛第1场

1003 吉哥系列故事——恨7不成妻
 
Time Limit: 0.5 Seconds   Memory Limit: 65536K
 
单身!
依然单身！
吉哥依然单身！
DS级码农吉哥依然单身！
所以，他生平最恨情人节，不管是214还是77，他都讨厌！
吉哥观察了214和77这两个数，发现：
2+1+4=7
7+7=7*2
77=7*11
最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！
什么样的数和7有关呢？
如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——
1.整数中某一位是7；
2.整数的每一位加起来的和是7的整数倍；
3.这个整数是7的整数倍；

现在问题来了：吉哥想知道在一定区间内和7无关的数字的平方和。

Input
输入数据的第一行是case数T(1 <= T <= 50)，然后接下来的T行表示T个case;每个case在一行内包含两个正整数L, R(1 <= L <= R <= 10^18)。

Output
请计算[L,R]中和7无关的数字的平方和，并将结果对10^9 + 7 求模后输出。

Sample Input
3
1 9
10 11
17 17

Sample Output
236
221
0

*/

/*
解题报告：

这题的数据范围很大，如果直接模拟的话肯定超时，还有这题时限好像还是500MS的，故意搞不这样就是不让一般的暴力方法过这题。

这题和以前不一样的地方在他要求的是平方和，而不是和。以前求和还是好做的。

一般这种题目的话肯定是数位DP了。
第一种想法，上面有三个条件，我们可以先用上面的条件求出至少符合一个条件的数字平方和。这个要用一下容斥原理。比较麻烦。

我是直接把7这一位数字去掉，然后再加两维状态保存当前数字对7取余的结果，和每一位之和对7取余的结果。

下面说一下我的做法。
dp[i][j][p][q]表示长度为i的以j为首位的数字每一位数字之和对7取余是p,整个数字对7取余是q的平方和。

现问题的关键是如何通过dp[i-1][k][a][b]推出来dp[i][j][p][q]

我们可以观察，假设dp[i-1][k][a][b]里面的数字是
n1,n2,...n[T]     dp[i-1][k][a][b]这个状态下有T个数字是合法的

那么dp[i][j][p][q]状态下的数字就是
j*ten[i-1]+n1,j*ten[i-1]+n2，...j*ten[i-1]+n[T]
ten[i]代表10的i次方
他们的平方和就是
(j*ten[i-1]+n1)^2+(j*ten[i-1]+n2)^2+...+(j*ten[i-1]+n[T])^2
展开一下
T*(j*ten[i-1])^2+2*j*ten[i-1]*(n1+n2+...+n[T])+n1^2+n2^2+n3^2+...+n[T]^2

从上面的式子可以看出，要计算出平方和，还需要统计一下合法数字的个数，还有，这些合法数字的总和。

所以我们要分三步DP。
dp复杂度是O(20*10*10*7*7),对于50个数据还是可以接受的。
来自：chenwenwen0210 的百度空间
*/

#include<stdio.h>
#include<time.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef __int64 lld;
const int MAX = 510000;
const int INF = 1000000000;
const lld MOD = 1000000007;

lld dp[20][10][7][7] = {0};
lld cnt[20][10][7][7] = {0};
lld sum[20][10][7][7] = {0};
lld multi[10][10];
lld add[10][10];
lld ten[20];
lld tp[20];
void init() {
    lld i, j, p, q, k;
    lld a, b;

    cnt[0][0][0][0] = 1;
    //计算个数
    for(i = 1; i < 20; i++) {
        for(j = 0; j < 10; j++) {
            if(j == 7)continue;
            for(a = 0; a < 7; a++) {
                for(b = 0; b < 7; b++) {
                    if(cnt[i - 1][j][a][b] == 0)continue;

                    for(k = 0; k < 10; k++) {
                        if(k == 7)continue;
                        p = add[k][a]; //加起来对7取余

                        q = multi[k][ten[i - 1]]; //乘起来对7取余
                        q = add[q][b];

                        cnt[i][k][p][q] += cnt[i - 1][j][a][b];
                        if(cnt[i][k][p][q] >= MOD)cnt[i][k][p][q] -= MOD;

                    }
                }
            }
        }
    }

    //计算和
    for(i = 1; i < 20; i++) {
        for(j = 0; j < 10; j++) {
            if(j == 7)continue;
            for(a = 0; a < 7; a++) {
                for(b = 0; b < 7; b++) {

                    for(k = 0; k < 10; k++) {
                        if(k == 7)continue;
                        p = add[k][a];

                        q = multi[k][ten[i - 1]];
                        q = add[q][b];
                        lld z = k * tp[i - 1] % MOD;
                        sum[i][k][p][q] += cnt[i - 1][j][a][b] * z + sum[i - 1][j][a][b];
                        if(sum[i][k][p][q] >= MOD)sum[i][k][p][q] %= MOD;

                    }
                }
            }
        }
    }

    //计算平方和
    for(i = 1; i < 20; i++) {
        for(j = 0; j < 10; j++) {
            if(j == 7)continue;
            for(a = 0; a < 7; a++) {
                for(b = 0; b < 7; b++) {

                    for(k = 0; k < 10; k++) {
                        if(k == 7)continue;
                        p = add[k][a];

                        q = multi[k][ten[i - 1]];
                        q = add[q][b];
                        lld z = k * tp[i - 1] % MOD;
                        dp[i][k][p][q] += cnt[i - 1][j][a][b] * z % MOD * z + dp[i - 1][j][a][b] + 2 * z * sum[i - 1][j][a][b];
                        if(dp[i][k][p][q] >= MOD)dp[i][k][p][q] %= MOD;

                    }
                }
            }
        }
    }

}
lld split(lld bit[], lld n) {
    int i = 0;
    for(i = 0; n; i++) {
        bit[i] = n % 10;
        n /= 10;
    }
    return i;
}
bool ok(lld n) {
    if(n % 7 == 0)return false;
    lld sum = 0;
    while(n) {
        if(n % 10 == 7)return false;
        sum += n % 10;
        n /= 10;
    }
    if(sum % 7 == 0)return false;
    return true;
}
lld calc(lld n) {
    if(n == 0)return 0;
    lld bit[22], len;
    lld ret = 0;
    lld i, j, k, p, q, a, b;
    len = split(bit, n);

    if(ok(n))ret += n % MOD * (n % MOD) % MOD;

    for(i = 1; i < len; i++) {
        for(j = 1; j < 10; j++) {
            if(j == 7)continue;
            for(p = 1; p < 7; p++) {
                for(q = 1; q < 7; q++) {
                    ret += dp[i][j][p][q];
                    if(ret >= MOD)ret -= MOD;
                }
            }
        }
    }

    lld presum = 0; //前面各位和对7取余
    lld premod7 = 0; //前面组成数字对7取余
    lld pre = 0; //前面组成数字对MOD取余
    for(i = len; i >= 1; i--) {
        j = 0;
        if(i == len)j++;
        for(; j < bit[i - 1]; j++) {
            if(j == 7)continue;
            for(k = 0; k < 10; k++) {
                if(k == 7)continue;
                for(a = 0; a < 7; a++) {
                    for(b = 0; b < 7; b++) {
                        p = add[presum][j];
                        p = add[p][a];
                        if(p == 0)continue;

                        q = multi[premod7][10 - 7];
                        q = add[q][j];
                        q = multi[q][ten[i - 1]];
                        q = add[q][b];

                        if(q == 0)continue;
                        lld z = (pre * 10 + j) * tp[i - 1] % MOD;
                        ret += z * z % MOD * cnt[i - 1][k][a][b] + dp[i - 1][k][a][b] + 2 * z * sum[i - 1][k][a][b];
                        ret %= MOD;
                    }
                }
            }
        }

        if(bit[i - 1] == 7)break;

        pre = (pre * 10 + bit[i - 1]) % MOD;

        presum = add[presum][bit[i - 1]];

        premod7 = multi[premod7][10 - 7];
        premod7 = add[premod7][bit[i - 1]];
    }

    return ret;
}

int main() {
    lld n, m;
    int i, j;

    int T = 0;
    for(i = 0; i < 10; i++) {
        for(j = 0; j < 10; j++) {
            add[i][j] = (i + j) % 7;
            multi[i][j] = i * j % 7;
        }
    }
    ten[0] = 1;
    tp[0] = 1;
    for(i = 1; i < 20; i++) {
        ten[i] = ten[i - 1] * 10 % 7;
        tp[i] = tp[i - 1] * 10 % MOD;
    }

    init();

    scanf("%d", &T);
    while(T--) {
        scanf("%I64d%I64d", &n, &m);

        lld ans = 0;
        ans += calc(m);
        ans -= calc(n - 1);
        if(ans < 0)ans += MOD;
        printf("%I64d\n", ans);
    }
    return 0;
}