吉哥系列故事――恨7不成妻 HDU

思路和普通的DP不一样的是这里求的是满足条件的数的平方的和而数位DP只跟数每位是什么密切相关所以要开一个结构（多加一个数的和sum 和平方和qsum）存一下各个状态的和的情况

dp[pos][state1][state2].num 满足该状态的数有几个

dp[pos][state1][state2].sum 满足该条件的数的和是多少

dp[pos][state1][state2].qsum 满足该条件的数的平方的和是多少

详见注解主要是状态转移是和和平方和的转移公式

∑(Y + xi)^2 = ∑(Y^2 + 2 * Y * xi + xi^2) = n * Y^2 + 2 * Y * ∑xi + ∑ xi^2 利用该公式可以实现状态转移

tips:先写好公式再疯狂% 不然容易乱

参考：https://blog.csdn.net/qq_37025443/article/details/78472991

#include <cstdio>
#include <cmath>
#include <algorithm>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
const long long  MOD=(1e9)+7;
typedef long long ll;
ll sum;
int cnt;
ll a[100];
int t[300];
struct Node{
 ll num,sum,qsum;
 Node(ll a=0,ll b=0,ll c=0):num(a),sum(b),qsum(c){

 }
}dp[20][200][10];

ll c[25];
void init(){
 c[0]=1;
 for(int i=1;i<=20;i++)c[i]=(c[i-1]*10)%MOD;
}

Node dfs(int pos,int state1,int state2,bool limit ){         
    if(pos==-1){    
   return Node(state1&&state2,0,0);
    }
    if(!limit&&dp[pos][state1][state2].qsum!=0)return dp[pos][state1][state2];
    int up=limit?a[pos]:9;
    Node ans;
    for(int i=0;i<=up;i++){
    //    cout<<i<<endl;
        if(i==7)continue;
        Node tmp=dfs(pos-1,(state1+i)%7,(state2*10+i)%7,limit&&i==up);
    //    cout<<111<<endl;
        ans.num=(ans.num+tmp.num)%MOD;//满足的数求和
        ans.sum=(ans.sum+(((i*c[pos])%MOD*tmp.num)%MOD+tmp.sum)%MOD)%MOD;//tmp.num*i*c[pos] 表示当前位pos的数的大小 乘以 一共有多少个满足条件数  tmp.sum表示pos-1的数的和 
        ans.qsum+=((tmp.qsum+(2*i*c[pos])%MOD*tmp.sum)%MOD)%MOD;//  平方和公式实现状态转移 tmp.qsum 就是a^2 2*i*c[pos]*tmp.sum 就表示 2*a*b
        ans.qsum%=MOD;
        ans.qsum+=(((i*c[pos]*i)%MOD*c[pos])%MOD*tmp.num)%MOD;//  i*i*c[pos]*c[pos] b^2 由上面的注解可以知道还需要求和 (n就是tmp.num）   
        ans.qsum%=MOD;
        
    }
    if(!limit) dp[pos][state1][state2]=ans;
    return ans;
}


ll solve(ll x){
  int pos=0;
  while(x){                                    
      a[pos++]=x%10;
      x/=10;
  }
 return  dfs(pos-1,0,0,1).qsum; 
}

int main()
{
ll a,b;
int t;
cin>>t;
int kase=1;
init();
    while(t--){
        cin>>a>>b;
        printf("%I64d
",(solve(b)-solve(a-1)+MOD)%MOD);
    }

    return 0;
}

吉哥系列故事――恨7不成妻 HDU

相关推荐