题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3709
题意:求区间[L,R]内每一个数中是否存在一位,使得左边的各位数*距离=右边的各位数*距离(自己和自己的距离算0)。
先枚举pivot的位置,然后做数位dp,记录当前数位、pv的位置和当前和。由于前导零的存在,最后结果要减掉诸如00,000,000...0这样的情况(个数和数位长度相同,当然单独一个0是合法的)。
最终结果ret-pos+1
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
int digit[maxn];
LL l, r;
LL dp[maxn][maxn][maxn**]; LL dfs(int l, int pv, int s, bool flag) {
if(l == ) return !s;
if(s < ) return ;
if(~dp[l][pv][s] && !flag) return dp[l][pv][s];
int pos = flag ? digit[l] : ;
LL ret = ;
for(int i = ; i <= pos; i++) {
ret += dfs(l-, pv, s+i*(l-pv), flag&&(i==pos));
}
if(!flag) dp[l][pv][s] = ret;
return ret;
} LL f(LL x) {
int pos = ;
if(x == -) return ;
while(x) {
digit[++pos] = x % ;
x /= ;
}
LL ret = ;
for(int i = pos; i >= ; i--) {
ret += dfs(pos, i, , true);
}
return ret - pos + ;
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
memset(dp, -, sizeof(dp));
while(T--) {
scanf("%I64d %I64d", &l, &r);
printf("%I64d\n", f(r)-f(l-));
}
return ;
}