Day9 - J - 吉哥系列故事——恨7不成妻 HDU - 4507

时间：2021-09-08 09:09:21
单身!
　　依然单身！
　　吉哥依然单身！
　　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

思路：还是数位DP，套用模板，求的是平方和，记录其后数位满足条件的个数即可，比如233, 234, 235满足，则平方和为(200+33)^2+(200+34)^2+(200+35)^2 = 3*200^2 + 2*200*(33+34+35)+33^2+34^2+35^2,记录下每次的和与平方和维护即可
typedef long long LL;

typedef pair<LL, LL> PLL;

const int MOD = 1e9+;

struct Node {

    LL num, sum, ssum;

} dp[][][];

LL a[], p[];

Node dfs(int pos, int pre, int presum, bool limit) {

    if(pos == -) {

        Node ret;

        ret.num = (pre !=  && presum != );

        ret.sum = ret.ssum = ;

        return ret;

    }

    if(!limit && dp[pos][pre][presum].num != -) return dp[pos][pre][presum];

    int up = limit?a[pos]:;

    Node ans;

    ans.num = ans.sum = ans.ssum = ;

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

        if(i == ) continue;

        Node nex = dfs(pos-, (pre+i)%, (presum*+i)%, limit&&i==a[pos]);

        if(nex.num == ) continue;

        ans.num = ((ans.num + nex.num) % MOD + MOD) % MOD;

        ans.sum = ((ans.sum + nex.sum + (p[pos]*i)%MOD*nex.num) % MOD + MOD) % MOD;

        ans.ssum = ((ans.ssum + nex.ssum + ((*p[pos]*i) % MOD)*nex.sum) % MOD + MOD) % MOD;

        ans.ssum = ((ans.ssum + (p[pos]*nex.num)%MOD * p[pos] % MOD *i*i) % MOD + MOD) % MOD;

    }

    if(!limit) dp[pos][pre][presum] = ans;

    return ans;

}

LL solve(LL n, LL m) {

    int pos = ;

    while(n) {

        a[pos++] = n % ;

        n /= ;

    }

    LL t1 = dfs(pos-, , , true).ssum;

    pos = ;

    while(m) {

        a[pos++] = m % ;

        m /= ;

    }

    t1 = dfs(pos-, , , true).ssum - t1;

    return (t1%MOD+MOD)%MOD;

}

void run_case() {

    LL n, m;

    cin >> n >> m;

    cout << solve(n-, m) << "\n";

}

int main() {

    ios::sync_with_stdio(false), cin.tie();

    int t;

    cin >> t;

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

        for(int j = ; j < ; ++j)

            for(int k = ; k < ; ++k)

                dp[i][j][k].num = -;

    p[] = ;

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

        p[i] = (p[i-]*)%MOD;

    while(t--)

        run_case();

    return ;

}
相关文章