吉哥系列故事——恨7不成妻（数位dp)

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

吉哥系列故事——恨7不成妻

传送门

Problem Description

　　单身!

　　依然单身！

　　吉哥依然单身！

　　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无关的数字的平方和。

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

解题思路：

dp[i][j][k]表示第i位，各位数和%7=j,前面的数字%7=k的状态

记录与7无关的数的个数\(sum\),与7无关的数和\(qsum\),以及平方和\(sqsum\)

与7无关的数的平方和=\(\sum(i*10^{pos}+num)^2=i*i*10^{2*pos}*sum+2*i*10^{pos}*qsum+sqsum\)

代码：

#include <bits/stdc++.h>

using namespace std;

/*    freopen("k.in", "r", stdin);

    freopen("k.out", "w", stdout); */

//clock_t c1 = clock();

//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define de(a) cout << #a << " = " << a << endl

#define rep(i, a, n) for (int i = a; i <= n; i++)

#define per(i, a, n) for (int i = n; i >= a; i--)

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> PII;

typedef pair<double, double> PDD;

typedef vector<int, int> VII;

#define inf 0x3f3f3f3f

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll MAXN = 1e6 + 7;

const ll MAXM = 1e6 + 7;

const ll MOD = 1e9 + 7;

const double eps = 1e-6;

const double pi = acos(-1.0);

int a[105];

/* 　　1、整数中某一位是7；

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

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

struct node

{

    ll sum;   //与7无关的数的个数

    ll qsum;  //与7无关的数和

    ll sqsum; //ans

    node(ll _sum = -1, ll _qsum = 0, ll _sqsum = 0) { sum = _sum, qsum = _qsum, sqsum = _sqsum; }

};

node dp[30][15][15];

ll c[20];

node dfs(int pos, int sta1, int sta2, bool lim) //sta1各位数和%7 sta2前面%7

{

    if (pos < 0)

        return node(sta1 && sta2, 0, 0);

    if (!lim && dp[pos][sta1][sta2].sum != -1)

        return dp[pos][sta1][sta2];

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

    node ret = node(0, 0, 0);

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

    {

        if (i != 7)

        {

            node t = dfs(pos - 1, (sta1 + i) % 7, (sta2 * 10 + i) % 7, lim && i == a[pos]);

            ret.sum += t.sum;

            ret.sum %= MOD;

            ret.qsum += (((c[pos] * i % MOD) * t.sum % MOD) + t.qsum) % MOD;

            ret.qsum %= MOD;

            ret.sqsum += t.sqsum % MOD;

            ret.sqsum %= MOD;

            ret.sqsum += ((i * i * c[pos] % MOD) * c[pos] % MOD) * t.sum % MOD;

            ret.sqsum %= MOD;

            ret.sqsum += ((i * 2 * c[pos] % MOD) * t.qsum) % MOD;

            ret.sqsum %= MOD;

        }

    }

    if (!lim)

        dp[pos][sta1][sta2] = ret;

    return ret;

}

ll solve(ll x)

{

    int pos = -1;

    while (x)

    {

        a[++pos] = x % 10;

        x /= 10;

    }

    return dfs(pos, 0, 0, true).sqsum;

}

void init()

{

    c[0] = 1;

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

        c[i] = (c[i - 1] * 10) % MOD;

}

int main()

{

    int t;

    init();

    scanf("%d", &t);

    while (t--)

    {

        ll L, R;

        scanf("%lld%lld", &L, &R);

        printf("%lld\n", ((solve(R) - solve(L - 1)) % MOD + MOD) % MOD);

    }

    return 0;

}

相关文章