推公式的能力需要锻炼。。
/* dp的时候要存结构体 里面三个元素： cnt，就是满足条件的个数 sum1，就是满足条件的数字和 sum2，满足条件的数字平方和 推导过程：还是用记忆化搜索模板 dp[pos][mod1][mod2]:后pos位模7=mod1，数位和模7=mod2的状态 设当前状态cur 枚举当前位i，碰到7跳过 求出后pos-1位的状态nxt 这里需要建立当前数的模型： 设x是后pos-1位的数：i*10^len+x; cur.cnt+=nxt.cnt; cur.sum1+=nxt.sum1+nxt.cnt*(i*10^(pos-1)) cur.sum2+=sum{ (i*10^len+x)^2 }= sum{ (i*10^len)^2 }+sum{ x^2 }+sum{ 2*x*i*10^len } 化简上式：sum{ x^2 }=nxt.sum2, sum{ 2*x*i*10^len }=nxt.sum1*2*i*10^len sum{ (i*10^len)^2 }=nxt.cnt*(i*10^len) */ #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 struct Node{ ll cnt,sum1,sum2; Node(){cnt=-1;sum1=sum2=0;} Node(ll cnt,ll sum1,ll sum2):cnt(cnt),sum1(sum1),sum2(sum2){} }dp[20][8][8]; ll a[20],f[20]; Node dfs(ll pos,ll mod1,ll mod2,ll lim){ if(pos<=0) return mod1&&mod2?Node(1,0,0):Node(0,0,0);//% 7 ≠0 即可 if(!lim && dp[pos][mod1][mod2].cnt!=-1)return dp[pos][mod1][mod2]; int num=lim?a[pos]:9; Node cur;cur.cnt=0; for(int i=0;i<=num;i++){ if(i==7)continue; Node nxt=dfs(pos-1,(mod1*10+i)%7,(mod2+i)%7,lim&&i==num); cur.cnt=(cur.cnt+nxt.cnt)%mod; cur.sum1=((cur.sum1+nxt.sum1)%mod+nxt.cnt*(i*f[pos]%mod)%mod)%mod; ll tmp1=nxt.sum1*2%mod*i%mod*f[pos]%mod; ll tmp2=nxt.cnt*(i*f[pos]%mod)%mod*(i*f[pos]%mod)%mod; cur.sum2=((cur.sum2+nxt.sum2)%mod+(tmp1+tmp2%mod)%mod)%mod; } if(!lim)dp[pos][mod1][mod2]=cur; return cur; } ll query(ll x){ int len=0; while(x){a[++len]=x%10;x/=10;} return dfs(len,0,0,1).sum2; } int main(){ f[1]=1;for(int i=2;i<=19;i++)f[i]=f[i-1]*10%mod; ll A,B,t;cin>>t; while(t--){ cin>>A>>B; cout<<(query(B)-query(A-1)+mod)%mod<<endl; } }
转载于:https://www.cnblogs.com/zsben991126/p/10730041.html
