BZOJ3598 [Scoi2014]方伯伯的商场之旅

题目名字好长。

当年在考场上只会分块打表的题。

前几天有人讲之后觉得大概可做。而且好像那个方法很优秀。

于是我难得地去写了一回不用记搜且不记上界的数位dp。感觉这个玩意写出来很短，但是思考和调试的复杂度变高了。我觉得是状态定义变得不明确的原因。也许再补一些题就好了。

考虑先让所有都合并到最低位，一个基础数位dp。（然后写丑了好久）

然后考虑如果把一个数字的集合位置从p移动到p+1，设这个数字从低位到高位是a[0]..a[n-1]，那么贡献就是∑a[0..p]-∑a[p+1..n-1]。显然当p从右往左移动的时候它是会先负后正的。如果它负的话就减，否则就不玩了。可以发现它们互相不影响。于是对于每一个p单独计算一遍贡献就行了。

然后还是没有原版跑得快。OTL。

#define PROC "shop"
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (long long int)

const int maxn = 53;
const int maxm = 509;
const int mb = 253;

dint l, r;
int n, m, bs, a[maxn];

dint dpBeginning() {
	static dint f[maxn], c[maxn], g[maxn], cr[maxn];
	c[0] = bs;
	f[0] = 0;
	for (int i = 1; i < n; ++ i) {
		c[i] = c[i - 1] * bs;
		f[i] = f[i - 1] * bs;
		for (int j = 1; j < bs; ++ j)
			f[i] = f[i] + c[i - 1] * i * j;
	}
	cr[0] = g[0] = 0;
	cr[1] = a[0] + 1;
	g[1] = a[1] * cr[1];
	for (int i = 2; i <= n; ++ i)  {
		cr[i] = g[i] = 0;
		for (int d = 0; d < a[i - 1]; ++ d) {
			cr[i] += c[i - 2];
			g[i] += f[i - 2] + c[i - 2] * (d * (i - 1) + a[i] * i);
		}
		cr[i] += cr[i - 1];
		g[i] += cr[i - 1] * a[i] * i + g[i - 1];
	}
	return g[n];
}

dint dp(dint v) {
	static dint c[maxn][maxm];
	static dint cr[maxn][maxm];
	m = 0;
	for (n = 0; v; v /= bs)
		a[n ++] = v % bs;
	a[n] = 0;
	m = n * bs;
	dint ans(dpBeginning());
	//printf(lld "\n", ans);
	for (int p = 1; p < n; ++ p) {
		memset(c, 0, sizeof(c));
		for (int i = 0; i < bs; ++ i)
			c[0][mb - i] = 1;
		for (int i = 1; i < n; ++ i)
			for (int j = mb - m; j <= mb + m; ++ j)
				if (c[i - 1][j])
					for (int d = 0; d < bs; ++ d) {
						int t((i < p) ? j - d : j + d);
						c[i][t] += c[i - 1][j];
					}
		memset(cr, 0, sizeof(cr));
		cr[0][mb - a[0]] = 1;
		for (int i = 1; i <= n; ++ i) {
			for (int d = 0; d < a[i - 1]; ++ d)
				if (i > 1) {
					for (int j = mb - m; j <= mb + m; ++ j)
						if (c[i - 2][j]) {
							int t((i - 1 < p) ? j - d : j + d);
							t = (i < p) ? t - a[i] : t + a[i];
							cr[i][t] += c[i - 2][j];
						}
				}
				else  {
					int t((i < p) ? mb - d - a[i] : mb - d + a[i]);
					++ cr[i][t];
				}
			for (int j = mb - m; j <= mb + m; ++ j)
				if (cr[i - 1][j]) {
					int t((i < p) ? j - a[i] : j + a[i]);
					cr[i][t] += cr[i - 1][j];
				}
		}
		for (int i = 1; i <= m; ++ i)
			ans -= cr[n][i + mb] * i;
	}
	return ans;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen(PROC ".in", "r", stdin);
	freopen(PROC ".out", "w", stdout);
#endif

	scanf(lld lld "%d", &l, &r, &bs);
	printf(lld "\n", dp(r) - dp(l - 1));
}