【数位DP+数学关系推导】吉哥系列故事——恨7不成妻 HDU - 4507

我就是我 2022-06-08 13:40 136阅读 0赞

Think:  
1知识点：数位DP+数学关系推导  
2题意：计算一个区间内和7无关的数的平方和，和7有关的定义为：  
（1）：整数中某一位是7；  
（2）：整数的每一位加起来的和是7的整数倍；  
（3）：这个整数是7的整数倍；  
3反思：  
（1）：细心数学关系的推导  
（2）：合适位置取模  
4解题思路：  
![参考博客地址：<a href=][a href]http://www.cnblogs.com/fu3638/p/6941006.html” title=”” />

vjudge题目链接

[建议参考博客1][1]  
[建议参考博客2][2]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    const LL mod = 1000000007;
    
    struct node{
        LL cnt;
        LL sum;
        LL sqsum;
    }dp[24][14][14];
    
    int tp, link[24];
    LL power[24];
    
    node dfs(int pos, LL num, LL dig, bool is_max);
    LL solve(LL x);
    
    int main(){
        for(int i = 0; i < 24; i++){
            for(int j = 0; j < 14; j++){
                for(int k = 0; k < 14; k++)
                    dp[i][j][k].cnt = -1;
            }
        }
        power[0] = 1;
        for(int i = 1; i <= 18; i++)
            power[i] = (power[i-1]*10)%mod;
        int T;
        LL l, r, ans;
        scanf("%d", &T);
        while(T--){
            scanf("%lld %lld", &l, &r);
            ans = (solve(r)-solve(l-1)+mod)%mod;
            printf("%lld\n", ans);
        }
        return 0;
    }
    LL solve(LL x){
        int tp = 0;
        while(x){
            link[tp++] = x%10;
            x /= 10;
        }
        node ans = dfs(tp-1, 0, 0, true);
        return ans.sqsum;
    }
    node dfs(int pos, LL num, LL dig, bool is_max){
        if(pos == -1){
            node tmp;
            tmp.cnt = (num && dig);
            tmp.sum = tmp.sqsum = 0;
            return tmp;
        }
        if(!is_max && ~dp[pos][num][dig].cnt)
            return dp[pos][num][dig];
        node ans, tmp;
        ans.cnt = ans.sum = ans.sqsum = 0;
        int is_top = 9;
        if(is_max)
            is_top = link[pos];
        for(LL i = 0; i <= is_top; i++){
            if(i == 7) continue;
            tmp = dfs(pos-1, (num*10+i)%7, (dig+i)%7, is_max && i == is_top);
    
            ans.cnt = (ans.cnt + tmp.cnt)%mod;
    
            ans.sum = (ans.sum + tmp.sum + (i*power[pos] %mod)*tmp.cnt %mod) %mod;
    
            ans.sqsum = (ans.sqsum + tmp.sqsum/*下一位平方和*/ + (LL)2*i*power[pos] %mod *tmp.sum %mod) %mod;
            ans.sqsum = (ans.sqsum + i*i*power[pos] %mod *power[pos] %mod *tmp.cnt %mod) %mod;
        }
        if(!is_max)
            dp[pos][num][dig] = ans;
        return ans;
    }

[a href]: /images/20220608/272fd684fcc2440a9bf856969d56734c.png
[1]: http://www.cnblogs.com/fu3638/p/6941006.html
[2]: http://blog.csdn.net/u011345136/article/details/38121135