杠杆数

看了一天的二分图&可撤销并查集(因为没找到合适的博客,很浪费时间).水一发数位dp(表示我今天做了题),这个题目贼套路...具体看注释...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=20,M=2000;
ll f[N][N][M];//到了i这个位子,支柱是j,和为k且没有限制的数的个数.
int a[N];
ll dfs(int len,int pos,int sum,bool limit)//同dp定义,limit表示这位有没有限制.
{
    if(len==0)  return sum==0;
    if(sum<0)   return 0;
    if(!limit&&f[len][pos][sum]!=-1)    return f[len][pos][sum];
    //三个数位dp而已.
    ll temp=0;
    int up=limit?a[len]:9;
    for(int i=0;i<=up;i++)  temp+=dfs(len-1,pos,sum+i*(len-pos),limit&&(up==i));
    if(!limit)  f[len][pos][sum]=temp;
    return temp;
}

ll solve(ll x)//分解x并对于位数做dfs
{
    int len=0;
    while(x)
    {
        a[++len]=x%10;
        x/=10;
    }ll ans=0;
    for(int i=1;i<=len;i++) ans+=dfs(len,i,0,1);
    return ans-len+1;
}

int main()
{
    ll l,r;
    cin>>l>>r;
    memset(f,-1,sizeof f);
    cout<<solve(r)-solve(l-1)<<endl;
    return 0;
}