1. 首页
2. 数位DP
3. 本页

HDU 4507 恨7不成妻 (数位DP)

题目大意：求指定范围内与7不沾边的所有数的平方和。通常的数位dp只是用来统计条件个数的，由于是求条件数的平方和，所以需要在过程中维护平方和。

解题思路：(以下内容来自互联网)

与7不沾边的数需要满足三个条件。

①不出现7

②各位数和不是7的倍数

③这个数不是7的倍数

这三个条件都是基础的数位DP。

但是这题要统计的不是符合条件个数，而是平方和。

也就是说在DP时候，要重建每个数，算出平方，然后求和。

需要维护三个值（推荐使用结构体）, 假定dfs推出返回的结构体是next，当前结果的结构体是ans

①符合条件数的个数 cnt

②符合条件数的和 sum

③符合添加数的平方和 sqsum

其中①是基础数位DP。②next.sum+(10^len*i)*ans.cnt，其中(10^len*i)*ans.cnt代表以len为首位的这部分数字和。

③首先重建一下这个数，(10^len*i+x),其中x是这个数的后面部分，则平方和就是(10^len*i)^2+x^2+2*10^len*i*x，其中x^2=next.sqsum

整体还要乘以next.cnt，毕竟不止一个。

这样sqsum+=next.sqsum

sqsum+=(2*10^len*i*x)*next.cnt=(2*10^len*i)*next.sum(神奇的化简）

sqsum+=(10^len*i)^2*next.cnt

然后就是本题鬼畜的地方了，cnt,sum,sqsum,三个都是达到了int64极限。

也即是说凡是这三个值参与运算的地方，都要狠狠打上mod，尤其是cnt！一坨坨mod出现了。

mod之后统计函数也有个小陷阱，那就是f(r)在mod之后有可能小于f(l-1)。也就是要对负数取正数模。

负数取模的方法（ans%mod+mod)%mod。

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const LL MOD = 1e9+7;
#define mod 1000000007LL
const int MAXN = 320000+10;

struct my
{
    LL cnt,sum,sqsum;
    my()
    {
        cnt=-1;
        sum=0;
        sqsum=0;
    };
    my(LL cnt1,LL sum1,LL sqsum1):cnt(cnt1),sum(sum1),sqsum(sqsum1) {};
} dp[20][20][20];
int dig[20];
LL p[25];

my dfs(int len,int asum,int beis,bool mxl)
{
    if(!len)
    {
        return asum!=0&&beis!=0?my(1,0,0):my(0,0,0);
    }

    if(!mxl && dp[len][asum][beis].cnt!=-1)
    {
        return dp[len][asum][beis];
    }
    //LL res=0;
    my now;
    now.cnt=0;
    int maxpos=mxl?dig[len]:9;
    for(int i=0; i<=maxpos; ++i)
    {
        if(i==7)
        {
            continue;
        }
        my next=dfs(len-1,(asum+i)%7,(beis*10+i)%7,mxl && i==maxpos);
        now.cnt+=next.cnt;
        now.cnt%=MOD;
        now.sum+=(next.sum+(p[len]*i%MOD)*next.cnt%MOD)%MOD;
        now.sum%=MOD;
        now.sqsum+=(next.sqsum+((2*p[len]*i)%MOD)*next.sum)%MOD;
        now.sqsum%=MOD;
        now.sqsum+=((next.cnt*p[len])%MOD*p[len]%MOD*i*i%MOD);
        now.sqsum%=MOD;
    }
    if(!mxl )
    {
        dp[len][asum][beis]=now;
    }
    return now;
}


LL solve(LL x)
{
    memset(dig,0,sizeof(dig));
    int len=0;
    while(x)
    {
        dig[++len]=x%10;
        x/=10;
    }
    my ans=dfs(len,0,0,true);
    //cout<<ans.sqsum<<endl;
    return ans.sqsum;
}

int main()
{
    p[1]=1;
    for(int i=2; i<=20; ++i)
    {
        p[i]=(p[i-1]*10)%MOD;
    }
    LL l,r;
    int t;
    cin>>t;
    //memset(dp,-1,sizeof(dp));
    while(t--)
    {
        cin>>l>>r;
        cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;
    }
    return 0;
}