算法分析
首先把问题转化为求解小于等于 $n$ 的数有几个符合要求
考虑如何设计状态
一个数只会有一个支点
因此我们可以枚举支点的位置去统计答案,这样也不会重复
支点固定了之后,算力矩就简单了
左右的力矩和需要算出,并且到最后要判断是否相等
简单起见我们只需维护 左力矩和 - 右力矩和
,最后判断是否为 0
即可
记 dp[i][j][x][s]
表示到从最高位开始的第 $i$ 位为止,前 $i$ 位数是否和 $n$ 的对应位上的数匹配,支点为 $x$,左力矩-右力矩
为 $s$ 的数字个数
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i = -~i)
using namespace std;
using ll = long long;
ll memo[20][2][20][1600];
void solve() {
ll l, r;
cin >> l >> r;
l = ~-l;
auto work = [&](ll n) -> ll {
if (n < 0) return 0;
if (n == 0) return 1;
vector<int> digit;
while (n) {
digit.push_back(n%10);
n /= 10;
}
int m = digit.size();
auto f = [&](auto& f, int i, int j, int x, int s) -> ll {
if (i == -1) return s == 0;
if (s < 0) return 0;
if (~memo[i][j][x][s]) return memo[i][j][x][s];
int ed = j ? 9 : digit[i];
ll now = 0;
rep(d, ed+1) now += f(f, i-1, j or d < ed, x, s+d*(i-x));
return memo[i][j][x][s] = now;
};
memset(memo, -1, sizeof memo);
ll res = 0;
rep(x, m) res += f(f, m-1, 0, x, 0);
return res-m+1;
};
ll ans = work(r) - work(l);
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
return 0;
}