#include <bits/stdc++.h>
using namespace std;
#define EOL '\n'
#define __LOG true
#ifdef __LOG
#define PRINTF printf
#else
#define PRINTF //
#endif
#define __IOFILE true
#ifdef __IOFILE
#define FREOPEN freopen
#else
#define FREOPEN //
#endif
const int offset = 1377;
int num[20];
bool vis[20][2 * offset + 1][2];
long long f[20][2 * offset + 1][2];
long long dfs(int now, int cnt, int piv, int sum, bool lim)
{
if (now > cnt)
{
return (long long)(!sum);
}
if (vis[now][sum + offset][lim])
{
return f[now][sum + offset][lim];
}
vis[now][sum + offset][lim] = true;
for (int digit = (now == 1); digit < 10 && (!lim || digit <= num[now]); ++digit)
{
f[now][sum + offset][lim] += dfs(now + 1, cnt, piv, sum + (piv - now) * digit, lim && digit == num[now]);
}
return f[now][sum + offset][lim];
}
long long calc(long long x)
{
if (x < 10)
{
return x;
}
int cnt = 0;
while (x)
{
num[++cnt] = x % 10;
x /= 10;
}
reverse(num + 1, num + cnt + 1);
int ret = 9;
for (int i = 2; i < cnt; ++i)
{
for (int j = 1; j < i; ++j)
{
memset(vis, false, sizeof vis);
memset(f, 0, sizeof f);
ret += dfs(1, i, j, 0, false);
}
}
for (int j = 1; j < cnt; ++j)
{
memset(vis, false, sizeof vis);
memset(f, 0, sizeof f);
ret += dfs(1, cnt, j, 0, true);
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long l, r;
cin >> l >> r;
cout << calc(r) - (l == 1? 0 : calc(l - 1)) << EOL;
return 0;
}
大致的思路就是枚举长度 cnt 和支点 piv,然后记搜
第一个调对的悬 1 关