HDU4507.吉哥系列故事——恨7不成妻（数位DP）

HDU4507

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

1、整数中某一位是7。

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

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

要求一个区间中和7无关的数的平方和。

需要用数位DP维护3个值：

1、与7无关的数的个数。

2、与7无关的数的和。

3、与7无关的数的平方和。

 

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
struct node {
    long long cnt;//与7无关的数的个数 
    long long sum;//与7无关的数的和 
    long long sqsum;//平方和 
}f[20][20][20];//分别是处理的数位、数字和%7、数%7
int bit[20];
long long p[20];//p[i]=10^i
node dfs (int pos,int pre1,int pre2,bool flag) {
    if (pos==-1) {
        node tt;
        tt.cnt=(pre1!=0&&pre2!=0);
        tt.sum=tt.sqsum=0;
        return tt;
    }
    if (!flag&&f[pos][pre1][pre2].cnt!=-1) {
        return f[pos][pre1][pre2];
    }
    int ed=flag?bit[pos]:9;
    node ans,tt;
    ans.cnt=ans.sqsum=ans.sum=0;
    for (int i=0;i<=ed;i++) {
        if (i==7) continue;
        tt=dfs(pos-1,(pre1+i)%7,(pre2*10+i)%7,flag&&i==ed);
        ans.cnt+=tt.cnt;
        ans.cnt%=mod;
        
        ans.sum+=(tt.sum+((p[pos]*i)%mod)*tt.cnt%mod)%mod;
        ans.sum%=mod;
        
        ans.sqsum+=(tt.sqsum+((2*p[pos]*i)%mod)*tt.sum)%mod;
        ans.sqsum%=mod;
        
        ans.sqsum+=((tt.cnt*p[pos])%mod*p[pos]%mod*i*i%mod);
        ans.sqsum%=mod;
    }
    if (!flag) f[pos][pre1][pre2]=ans;
    return ans; 
}
long long calc (long long n) {
    int pos=0;
    while (n) {
        bit[pos++]=n%10;
        n/=10;
    }
    return dfs(pos-1,0,0,1).sqsum;
}
int main () {
    p[0]=1;
    for (int i=1;i<20;i++) {
        p[i]=p[i-1]*10;
        p[i]%=mod;
    }
    for (int i=0;i<20;i++) {
        for (int j=0;j<20;j++) {
            for (int k=0;k<20;k++) {
                f[i][j][k].cnt=-1;
            }
        }
    }
    int _;
    scanf("%d",&_);
    while (_--) {
        long long n,m;
        scanf("%lld%lld",&n,&m);
        long long ans=calc(m)-calc(n-1);
        ans=(ans+mod)%mod;
        printf("%lld
",ans);
    }
}