用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c代码库

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

2013-03-25 作者： 小蜜锋举报

[c]代码库

view sourceprint?
/*
 
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;
}


网友评论    (发表评论)

共1 条评论 1/1页

发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...