[HDU 6156] Palindrome Function

题意：
我们定义

求\(\sum_{i=L}^{R}\sum_{j=l}^{r}f(i, j)\)

题解：
题意很明显往数位\(dp\)去靠，但是要求回文串，所以要记录下前面枚举的数位的数字是什么。同时要注意到前导\(0\)的情况，这会让你枚举的数字长度减少。并且只要有一个地方没有对应上，该串就无法形成回文串。我们定义\(dp[len][pos][k][good]\)，代表当前枚举的数字长度为\(len + 1\)，枚举到第\(pos\)位，在\(k\)进制下，之前对应位置的数字若能对应则\(good\)置\(1\)，其余置\(0\)时，能提供的贡献是多少。当我们枚举到数位到达当前长度的一半以及更长时，进行对应位置的判断，从而将状态转移下去。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[37][37][37][2];
int pre[37], tot, n;
int a[37], cas;
int L, R, l, r;

ll dfs(int len, int pos, int k, int good, bool lim) {
	if (pos == -1) {
		if (good) return k;
		else return 1;
	}
	if (!lim && dp[len][pos][k][good]) {
		return dp[len][pos][k][good];
	}
	int to = lim? a[pos] : k - 1;
	ll tmp = 0;
	for (int i = 0; i <= to; ++i) {
		pre[pos] = i;
		if (i == 0 && len == pos && len) tmp += dfs(len - 1, pos - 1, k, good, lim && (i == to));
		else if (good && pos < (len + 1) / 2) tmp += dfs(len, pos - 1, k, i == pre[len - pos], lim && (i == to));
		else tmp += dfs(len, pos - 1, k, good, lim && (i == to));
	}
	if (!lim) dp[len][pos][k][good] = tmp;
	return tmp;
}

ll gao(int val, int k) {
	tot = 0;
	int v = val;
	while (v) {
		a[tot++] = v % k;
		v /= k;
	}
	return dfs(tot - 1, tot - 1, k, 1, true);
}

void solve() {
	scanf("%d %d %d %d", &L, &R, &l, &r);
	ll ans = 0;
	for (int k = l; k <= r; ++k) {
		ans += gao(R, k) - gao(L - 1, k);
	}
	printf("Case #%d: ", ++cas);
	printf("%lld\n", ans);
}

int main() {
	int t = 1;
	scanf("%d", &t);
	while (t--) solve();
	return 0;
} 

[HDU 6156] Palindrome Function

原文：https://www.cnblogs.com/Sstee1XD/p/14489230.html