HDU - 4507 - 吉哥系列故事——恨7不成妻（数位DP，数学）

时间：2021-12-28 09:07:06

链接：

https://vjudge.net/problem/HDU-4507

题意：

　　单身!

　　依然单身！

　　吉哥依然单身！

　　DS级码农吉哥依然单身！

　　所以，他生平最恨情人节，不管是214还是77，他都讨厌！

　　

　　吉哥观察了214和77这两个数，发现：

　　2+1+4=7

　　7+7=72

　　77=711

　　最终，他发现原来这一切归根到底都是因为和7有关！所以，他现在甚至讨厌一切和7有关的数！

　　什么样的数和7有关呢？

　　如果一个整数符合下面3个条件之一，那么我们就说这个整数和7有关——

　　1、整数中某一位是7；

　　2、整数的每一位加起来的和是7的整数倍；

　　3、这个整数是7的整数倍；

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

思路:

单纯的算个数就很简单。看了大佬博客发现除了麻烦点其他还好。

考虑数学公式。假如我们当前位是第p位，值为i，低位有a和b两个数满足条件。

如果要把a和b合并，首先可算出和im[p]cnt+a+b，cnt就是满足的个数，m是10的几次方。

这样就可以更新和。

再考虑平方，（a+b)^2 = a2+2*a*b+b2

所有就有im[p]sum2+sqr，其中sum是a+b，sqr是a2+b2,就是返回回来的平方和。

还要再加上(im[p])^2*cnt,要考虑返回回来的可行解数。

注意取模即可。

代码：

// #include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<vector>

#include<string.h>

#include<set>

#include<queue>

#include<algorithm>

#include<math.h>

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

const int MAXN = 1e6+10;

struct Node

{

    LL cnt, sum, sqr;

    Node()

    {

        cnt = -1;

        sum = sqr = 0;

    }

    Node(LL _cnt, LL _sum, LL _sqr): cnt(_cnt), sum(_sum), sqr(_sqr){}

}F[20][10][10];

int dig[20];

LL m[20];

LL a, b, n;

Node Dfs(int pos, LL sum1, LL sum2, bool lim)

{

    if (pos == -1)

    {

        if (sum1 != 0 && sum2 != 0)

            return Node(1, 0, 0);

        return Node(0, 0, 0);

    }

    if (!lim && F[pos][sum1][sum2].cnt != -1)

        return F[pos][sum1][sum2];

    int up = lim ? dig[pos] : 9;

    Node ans(0, 0, 0), tmp;

    for (LL i = 0;i <= up;i++)

    {

        if (i == 7)

            continue;

        tmp = Dfs(pos-1, (sum1+i)%7, (sum2*10+i)%7, lim && i == up);

        ans.cnt = (ans.cnt + tmp.cnt)%MOD;

        ans.sum = (ans.sum + (i*m[pos]%MOD*tmp.cnt%MOD + tmp.sum)%MOD)%MOD;

        ans.sqr = (ans.sqr + (i*m[pos]%MOD*2%MOD*tmp.sum%MOD+tmp.sqr)%MOD)%MOD;

        ans.sqr = (ans.sqr + (i*m[pos]%MOD)*(i*m[pos]%MOD)%MOD*tmp.cnt)%MOD;

    }

    if (!lim)

        F[pos][sum1][sum2] = ans;

    return ans;

}

LL Solve(LL x)

{

    int p = 0;

    while(x)

    {

        dig[p++] = x%10;

        x /= 10;

    }

    return Dfs(p-1, 0, 0, 1).sqr;

}

int main()

{

    // freopen("test.in", "r", stdin);

    m[0] = 1;

    for (int i = 1;i < 20;i++)

        m[i] = m[i-1]*10;

    int t;

    scanf("%d", &t);

    while(t--)

    {

        scanf("%lld %lld", &a, &b);

        printf("%lld\n", ((Solve(b)-Solve(a-1))%MOD+MOD)%MOD);

    }

    return 0;

}

相关文章