思路:首先要明白,每个数字的支点肯定是唯一的,这个很容易证明,因为假设在某一位置平衡了, 那么左移右移肯定就不平衡了,不存在第2个支点(全0特殊,要另外考虑)
所以可以枚举支点,然后做数位DP,dp[i][j]表示到第i位,和为j的情况,和可能为负,所以可以数组开两倍即可,然后注意,0的话,是会被计算len次的,所以答案还要减去len - 1,因为0的话,可以以任意点做支点,而答案只要一次即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int t; ll x, y; int bit[20], bn; void get(ll x) { bn = 0; while (x) { bit[bn++] = x % 10; x /= 10; } for (int i = 0; i < bn / 2; i++) swap(bit[i], bit[bn - i - 1]); } ll dp[20][4000]; ll solve(ll x) { if (x == -1) return 0; if (x == 0) return 1; get(x); ll ans = -bn + 1; for (int i = 1; i <= bn; i++) { memset(dp, 0, sizeof(dp)); int sum = 2000; for (int j = 0; j < bn; j++) { for (int k = 0; k < 4000; k++) { if (dp[j][k] == 0) continue; for (int x = 0; x < 10; x++) dp[j + 1][k + (i - (j + 1)) * x] += dp[j][k]; } for (int x = 0; x < bit[j]; x++) { dp[j + 1][sum + (i - (j + 1)) * x]++; } sum += (i - (j + 1)) * bit[j]; } if (sum == 2000) ans++; ans += dp[bn][2000]; } return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%lld%lld", &x, &y); printf("%lld\n", solve(y) - solve(x - 1)); } return 0; }