恨 7 不成妻

链接

因为求平方和，所以返回用了struct 来保存

然后进行了一系列诡诡奇奇的操作

以得到正确答案

唉~

#include<bits/stdc++.h>
#define re return
#define ll long long
#define inc(i,l,r) for(ll i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x)
{
    char c;bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

ll n,m,a,b,t,NUM[30],Pow[20];

struct node{
    ll cnt,sum,sqs;
}f[20][7][7];
ll mod=1000000007;

node dfs(ll pos,ll limit,ll num,ll sum)//num为数位和%7，sum为数字%7
{
    if(!pos)
    {
        re (node){(num!=0&&sum!=0)?1:0,0,0};
    }
    if(!limit&&(~f[pos][num][sum].cnt))re f[pos][num][sum];
    
    int up=limit?NUM[pos]:9;
    node res=(node){0,0,0};
    inc(i,0,up)
    {
        if(i==7)continue;
        ll lzx=i*Pow[pos]%mod;
        node tmp=dfs(pos-1,limit&&(up==i),(num+i)%7,(sum*10+i)%7);
        res.cnt=(res.cnt+tmp.cnt)%mod;
        res.sum=(res.sum+(tmp.sum+lzx*tmp.cnt)%mod)%mod;
        res.sqs=(res.sqs+2*lzx*tmp.sum+tmp.sqs+lzx*lzx%mod*tmp.cnt%mod)%mod;
    }
    
    if(!limit)f[pos][num][sum]=res;
    re res;
}
        /*copyde
        第len位填i f1,f2,f2...fN记录前len位已经填好的数字
        对答案的贡献为：  (f1+ i*10^(len-1) )^2+(f2+ i*10^(len-1) )^2+...+(fN+ i*10^(len-1) )^2
        将平方和展开 整理 提公因式:
        N*(i*10^(len-1))^2+ f1^2+f2^2+...+fN^2+ 2*(i*10^(len-1))*(f1+f2+...fN) 
        其中 N即为要求的s   2*(i*10^(len-1))*(f1+f2+...fN) 即为要求的sum   整一个即为sqrsum 
        */
ll cala(ll x)
{
    int len=0;
    do
    {
        NUM[++len]=x%10;
        x/=10;
    }while(x);
    
    node tmp=dfs(len,1,0,0);
    re tmp.sqs;
}

int main()
{
    freopen("in.txt","r",stdin);
    
    inc(i,0,19)inc(j,0,6)inc(k,0,6)f[i][j][k].cnt=-1;
    Pow[1]=1;
    inc(i,2,18)Pow[i]=(Pow[i-1]*10)%mod;
    
    int T;
    rd(T);
    while(T--)
    {
        rd(a),rd(b);
        ll ans=(cala(b)-cala(a-1)+mod)%mod;
        printf("%lld
",ans);
    }
    re 0;
}