最近发现数位dp其实挺常见的，这里会陆陆续续把自己见到的数位dp放在这里一起总结。
1 - G - Palindrome Function
定义函数$f(n,k)=k$，如果n在k进制是回文数。否则$f(n,k)=1$
多组询问，给定$L,R,l,r$，求
$$
\sum_{i=L}^R \sum_{j=l}^r f(i,j)
$$
其实基本可以上数位dp的板子，设dp[base][pos][mxlen]是在base进制，枚举到pos位，得到的数的最大长度是mxlen的条件下的回文数个数，即可解决。
值得注意的是，对于询问组数较少的数位dp，最好躲记录一些状态，比如dp[base][pos][mxlen][lead][lim]的形式。 这样可以在一次记忆化搜索时，避免因为边界条件而重新搜索。但是，这样的代价是我们必须在每一次搜索前将dp清为-1，因为此时dp的值与计算的数密切相关。如果是多组询问，我们自然希望之前的搜索结果能尽量发挥作用，所以我们选择少记几个状态，让dp的意义与之前搜索的边界条件无关，使得dp更加通用，避免了每次memset的麻烦。
#参考代码
|
|
using namespace std; |
typedef long long ll; |
inline void read(int &x) { |
char ch = getchar(); x = 0; |
while(!isdigit(ch)) ch = getchar(); |
while(isdigit(ch)) |
x = x * 10 + (ch ^ '0'), ch = getchar(); |
} |
int d[40], tmp[40]; |
int dp[40][40][40], base; |
int dfs(int pos, int mxlen, bool lead, bool lim) { |
if(pos == -1) return 1; |
if(dp[base][pos][mxlen] != -1 && !lead && !lim) return dp[base][pos][mxlen]; |
int up = lim ? d[pos] : base - 1; |
int res = 0; |
for(int i = 0; i <= up; ++i) { |
tmp[pos] = i; |
if(lead) // 有前导零，则要注意数的长度可能会变小 |
res += dfs(pos - 1, (mxlen - (i == 0)), i == 0, lim && i == up); |
else { |
if(pos >= mxlen / 2) // 前一半数随便填 |
res += dfs(pos - 1, mxlen, 0, lim && i == up); |
else if(i == tmp[mxlen - pos - 1]) // 后一半要和前一半对应 |
res += dfs(pos - 1, mxlen, 0, lim && i == up); |
} |
} |
return ((lim || lead) ? res : dp[base][pos][mxlen] = res); // 只有非特殊情况才能保留这个值 |
} |
ll solve(int x, int b) { |
int len = 0; base = b; |
// memset(dp, -1, sizeof dp); orz 不要在这里搞 |
while(x) { |
d[len++] = x % base; |
x /= base; |
} |
return dfs(len - 1, len, 1, 1); |
} |
int main() { |
int t; |
read(t); |
memset(dp, -1, sizeof dp); |
for(int cas = 1; cas <= t; ++cas) { |
int L, R, l, r; |
read(L), read(R), read(l), read(r); |
ll ans = 0; |
for(int i = l; i <= r; ++i) { |
ll res = solve(R, i) - solve(L - 1, i); |
ans += res * base + (R - L + 1 - res); |
} |
printf("Case #%d: %lld\n", cas, ans); |
} |
return 0; |
} |