题解 AT2582 [ARC075D] Mirrored

题意：给定 \(D\)，求满足 \(\mathrm{rev}(N)=N+D\) 的 \(N\) 的个数，\(\mathrm{rev}(N)\) 表示十进制下将 \(N\) 按位翻转并去掉前导 \(0\) 后的数。

为了更清楚地表示，我们设 \(|N|\) 为 \(N\) 的位数。

由于是将 \(N\) 翻转，我们直接将翻转前后的位置匹配算贡献。可以直接枚举 \(|N|\)，枚举每对的 高位减低位 的差，就能算出 \(\mathrm{rev}(N) - N\) 的值，如果 \(=D\) 将方案数计入答案即可。注意一些限制条件即可。这样的复杂度是 \(19^{\lfloor \frac{|N|+1}{2} \rfloor}\)。而这样就算我们吸氧，\(|N|\) 也只能枚举到 \(14\)，会 WA 4 个点。而 \(|N|\) 却是理论上 \(\le 18\) 的，可以自己证一下。

由于我们写的是搜索，自然可以想想怎么剪枝。我们发现每对的贡献都形如 \(99 \ldots 90 \ldots 00 \times c\)，其中 \(c\) 为高位减低位的差。更加具体地，如果当前高位距离最高位有 \(k\) 个数位，贡献为 \((10^{|N|-2\times k} - 1) \times 10^k\)。如果自己手推几个长度就能发现，由低到高贡献的跨度比每次 \(\times 10\) 还要大。这也就有一个问题：我们枚举匹配出的对时，按贡献从高到低枚举，偏差很难由低位补足。也就是说，满足条件的差的序列很少。这时可行性剪枝效果非常出色。我们只需要在上述做法加一个可行性剪枝即可无压力通过。

\(\text{Code}\)：

int d;
ll pw[20];
ll to[20][15];
ll suf[20][15];

ll dfs(int all, int nw, ll sum, ll res) {
	if(sum + suf[all][nw] < d || sum - suf[all][nw] > d) return 0;
	if(nw == (all >> 1)) {
		if(abs(d - sum) % (pw[all - nw] - pw[nw - 1]) || abs(d - sum) / (pw[all - nw] - pw[nw - 1]) > 9) return 0;
		int nd = (d - sum) / (pw[all - nw] - pw[nw - 1]);
		return res * (10 - abs(nd) - (nw == 1));
	}
	ll ret = 0;
	rep(i, -9, 9) {
		if(nw == 1 && i == -9) continue;
		ll nwp = (pw[all - nw] - pw[nw - 1]) * i;
		ret += dfs(all, nw + 1, sum + nwp, res * (10 - abs(i) - (nw == 1)));
	}
	return ret;
}

int main() {
	pw[0] = 1;
	rep(i, 1, 18) pw[i] = pw[i - 1] * 10;
	rep(i, 2, 18) rep(j, 1, (i >> 1)) to[i][j] = pw[i - j] - pw[j - 1];
	rep(i, 2, 18) per(j, (i >> 1), 1) suf[i][j] = suf[i][j + 1] + to[i][j] * 9;
	qread(d);
	ll ans = 0;
	rep(i, 2, 18) {
		if(i & 1) ans += 10 * dfs(i, 1, 0, 1);
		else ans += dfs(i, 1, 0, 1);
	}
	cout << ans << endl;
	return 0;
}