HUD 4507 吉哥系列故事—

传送门

三个限制都可以数位 $dp$ ， $dfs$ 是维护当前位，之前各位总和模 $7$ 意义下的值，之前填的数模 $7$ 意义下的值，是否贴着限制

主要现在求的是各个合法数的平方的和，比较恶心

开一个结构体维护一下三个东西，合法数的个数，合法数的和，合法数的平方和

前两个好维护，平方和发现其实可以拆开，比如下一层 $dfs$ 传上来的和为 $x$ ，当前位填的数为 $k$ ，考虑当前所有合法数的平方和看成每一个合法数的平方的和

设下一层某一个合法数传上来的值为 $y$，那么当前层的值即为

$10^p \cdot k + y$ ，平方后即为 $10^{2p} \cdot k^2 + y^2 + 2ky \cdot 10^p$

发现所有的 $y^2$ 加起来以后其实就是下一层的合法数的平方和

对于 $2ky \cdot 10^p$ ，把 $2k \cdot 10^p$ 提出来，那么也可以把所有 $y$ 加起来即为下一层的合法数的和

对于 $10^{2p} \cdot k^2$ ，因为加了下一层合法数的个数次，那么贡献即为下一层合法数数量乘 $10^{2p} \cdot k^2$

所以我们完全可以用下一层的数据维护出当前位的数据

具体实现可以看代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int mo=1e9+;

inline int fk(int x) { return x>=mo ? x-mo : x; }

ll T,L,R;

struct dat {

    ll tot,sum,sum2;

    dat (ll _tot=,ll _sum=,ll _sum2=) { tot=_tot,sum=_sum,sum2=_sum2; }

    inline dat operator + (const dat &tmp) const {

        return dat(fk(tot+tmp.tot),fk(sum+tmp.sum),fk(sum2+tmp.sum2));

    }

    inline dat operator * (const ll &tmp) const {

        return dat(tot, fk(tot*tmp%mo + sum) , fk( fk((tot*tmp%mo)*tmp%mo + (2ll*tmp%mo)*sum%mo) + sum2 ) );

    }

}f[][][][];

ll Power[];

vector <int> V;

dat dfs(int p,int sum,int now,bool lim)

{

    if(!p) return (sum&&now) ? dat(,,) : dat(,,);

    dat &t=f[p][sum][now][lim];

    if(t.tot!=-) return t;

    t.tot=;

    for(int k=;k<=;k++)

    {

        if(lim&&k>V[p-]) break;

        if(k==) continue;

        dat add=dfs(p-,(sum+k)%,(now*+k)%,lim&(k==V[p-]));

        t=t + ( add * (Power[p-]*k%mo) );

    }

    // cout<<p<<" "<<sum<<" "<<now<<" "<<lim<<" "<<t.tot<<" "<<t.sum<<" "<<t.sum2<<endl;

    return t;

}

inline void Clr()

{

    for(int i=;i<=;i++)

        for(int j=;j<;j++)

            for(int k=;k<;k++)

                f[i][j][k][]=f[i][j][k][]=dat(-,,);

}

int main()

{

    T=read();

    Power[]=; for(int i=;i<=;i++) Power[i]=Power[i-]*%mo;

    while(T--)

    {

        L=read()-,R=read();

        ll now=R; V.clear(); Clr();

        while(now) V.push_back(now%),now/=;

        ll ans=dfs(V.size(),,,).sum2;

        now=L; V.clear(); Clr();

        while(now) V.push_back(now%),now/=;

        printf("%d\n",fk(ans-dfs(V.size(),,,).sum2+mo));

    }

    return ;

}

巴特西

HUD 4507 吉哥系列故事——恨7不成妻

最新文章

热门文章