数位dp
对于数位上每个数的有约束的各类统计问题，可以考虑用数位 dp 解决。
通常使用记忆化递归实现（更通用），属于比较板子的 dp 了。
在进行记忆化递归时，通常需要考虑三个因素：前导零（有时需要考虑），值域边界限制（必定会有），题面要求限制。
例题
-
版子题，枚举 \(0 \sim 9\) 的数字，按位统计即可。
注意前导零对答案的影响。
代码：
ll a,b,f[15][15][11][2],w[15],n;
ll calc(ll pos,ll k,ll lead,ll limit,ll sum){
if(!lead&&!limit&&f[pos][sum][k][lead]!=-1) return f[pos][sum][k][lead];
if(pos>n) return sum;
ll res=0,up=9;
if(limit) up=w[pos];
for(int i=0;i<=up;i++){
res+=calc(pos+1,k,(lead==1&&i==0)?1:0,(limit==1&&i==up)?1:0,sum+(i==k)-(i==k&&i==0&&lead));
}
if(!limit&&!lead) f[pos][sum][k][lead]=res;
return res;
}
inline ll solve(ll k,ll now){
memset(f,-1,sizeof(f));
n=0;
if(k==0) w[++n]=0;
while(k){
w[++n]=k%10,k/=10;
}
reverse(w+1,w+1+n);
return calc(1,now,1,1,0);
}
-
题目的三个条件易于约束，但是求平方和难以直接转移。
考虑合并时的情况，从简单情况入手，前 \(pos-1\) 位已被固定（递归时进行统计），当前第 \(pos\) 位的数字为 \(i\)，对构成数字本身的贡献为 \(a\)，递归回来构成的数字为 \(b,c,\dots\)。
那么递归时的答案计算应是 \((a+b)^2+(a+c)^2+\dots\)，拆开来则是 \((a^2+2ab+b^2)+(a^2+2ac+c^2)+\dots\)。
那么我们在递归时，就要维护三个量：可以构成的数字个数 \(k_1\)（计算多个 \(a_2\)），当前对数字本身的贡献 \(k_2\)（计算多个类似 \(2ab\) 对答案的贡献），以及当前的数字平方和 \(k_3\)（计算多个平方对答案贡献）。
前两个量合并时直接相加即可，平方和合并便是 \(k_1a^2+2ak_2+k_3\)。
代码：
struct node{
ll sqsum,sum,cnt;
}f[25][10][10];
ll t,l,r,a[25],n,base[25],Base[25];
node calc(ll pos,ll sum,ll now,ll limit){
if(!pos) return {0,0,(sum&&now)};
if(!limit&&f[pos][sum][now].cnt!=-1) return f[pos][sum][now];
node res={0,0,0},tmp;
for(int i=0;i<=9;i++){
if(limit&&a[pos]<i) break;
if(i==7) continue;
tmp=calc(pos-1,(sum+i)%7,(now+i*Base[pos-1]%7)%7,limit&&a[pos]==i);
res.cnt=(res.cnt+tmp.cnt)%mod;
res.sum=(res.sum+tmp.sum+i*tmp.cnt%mod*base[pos-1]%mod);
res.sqsum=((res.sqsum+tmp.sqsum)%mod+2*tmp.sum%mod*i%mod*base[pos-1]%mod)%mod;
res.sqsum=(res.sqsum+tmp.cnt*i%mod*base[pos-1]%mod*i%mod*base[pos-1]%mod)%mod;
}
if(!limit) f[pos][sum][now]=res;
return res;
}
inline ll solve(ll x){
memset(f,-1,sizeof(f));
n=0;
if(x==0) a[++n]=0;
while(x){
a[++n]=x%10,x/=10;
}
return calc(n,0,0,1).sqsum;
}
-
根据题目定义，可以得到一个性质：
如果一个数是杠杆数，它的支点有且仅有一个。因为无论当前支点向左移还是向右移，左右的差必定单调递增，差必不为 \(0\)。
所以，只需要枚举每一个作为支点的位置，进行 dp，状态为三维：位数，支点左右差值，支点位置。最后判断差是否为 \(0\) 即可。