Codeforces Goodbye2016 G New Year and Binary Tree Paths 数学+DP

题目大意：给定一颗无穷大的完全二叉树，根节点的标号为$1$，对于每个节点若其标号为$x$，则其左儿子标号为$2x$，右儿子标号为$2x+1$。同时再给定$S$，求树上有多少条路径使得路径上节点的标号和恰为$S$。数据范围$S\leq{10^{15}}$。

做法：

首先考虑一条深度递增的链的情况，设深度最小的点标号为$x$，链上的点数为$h$，则如果都是左儿子（除了链顶）的话标号和为$(2^{h}-1)x$。

若链从下往上的第$i(1\leq{i}\leq{h-1})$个点是右儿子则会给标号和带来独立的$2^{i}-1$的贡献。

可以注意到$x$取值只能为$\lfloor\frac{S}{2^{h}-1}\rfloor$，这是因为如果$x$少$1$，即使所有的$h-1$个点都为右儿子带来的$\sum_{i=1}^{h-1}(2^{i}-1)=2^{h}-h\leq{2^{h}-1}$。

于是我们可以枚举$h$，算出$x$，先考虑全为左儿子，然后看看能否把某些节点修改为右儿子使得权值和为$S$，就是看看离$S$还差多少，从大到小进行贪心即可。若可以凑出就找到了一个解。

接下来考虑有分叉的情况，令lca的标号为$x$，设从lca左儿子开始向下的链长度为$h_1$，从lca右儿子开始向下的链长度为$h_2$，枚举$h_1,h_2$，假设lca左右儿子下面的节点均为左儿子则权值和为$x+(2^{h_1}-1)2x+(2^{h_2}-1)(2x+1)=(2^{{h_1}+1}+2^{{h_2}+1}-3)x+2^{h_2}-1$。

与上面同理可知$x$取值唯一，那么接下来就是将某些左儿子变成右儿子来凑成$S$，问题转化为用$2^{1}-1,2^{2},...,2^{{h_1}-1}-1,2^{1}-1,2^{2}-1,...,2^{{h_2}-1}-1$来凑成一个数$S'$，这个看起来不太好做，我们通过枚举一共选了多少个数来凑，将所有的数都$+1$，再将问题转化为用$2^{1},2^{2},...,2^{{h_1}-1},2^{1},2^{2},...,2^{{h_2}-1}$中的$n$个数来凑成$S'+n$。这可利用$O({h_1}{h_2})$的DP来解决，设$f[i][j][k]$表示前$i$位一共用了$j$个数，$k$表示是否向下一位进位的方案数，具体细节见代码。

总时间复杂度$O(\log^{5}S)$。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
void dec(ll &x, ll y) {
	if (x >= y)
		x -= y;
}
ll p(int x) {
	return 1ll << x;
}

ll f[51][101][2];
ll calc(ll s, ll x, int a, int b, int n) {
	if (s & 1)
		return 0;
	if (n == 0)
		return s == 0 ? 1 : 0;
	if (a == 1 && b == 1)
		return ((s - n) == (x * 5 + 1)) ? 1 : 0;
	memset(f, 0, sizeof f);
	f[0][0][0] = 1;
	for (int i = 1; i <= 50; ++i) {
		int d = (s >> i) & 1;
		for (int j = 0; j <= 2 * (i - 1); ++j) {
			for (int aa = 0; aa <= 1; ++aa) {
				if (aa == 1 && i >= a)
					continue;
				for (int bb = 0; bb <= 1; ++bb) {
					if (bb == 1 && i >= b)
						continue;
					for (int k = 0; k <= 1; ++k) {
						if ((k + aa + bb) % 2 == d)
							f[i][j + aa + bb][(k + aa + bb) / 2] += f[i - 1][j][k];
					}
				}
			}
		}
	}
	return f[50][n][0];
}

int main() {
	ll s;
	cin >> s;
	ll num = 0;
	for (int i = 1; i <= 50; ++i) {
		ll x = s / (p(i) - 1);
		if (x > 0) {
			ll last = s % (p(i) - 1);
			for (int j = i - 1; j >= 1; --j)
				dec(last, p(j) - 1);
			if (last == 0)
				++num;
		}
	}
	for (int h1 = 1; h1 <= 50; ++h1) {
		for (int h2 = 1; p(h2) - 1 <= s; ++h2) {
			ll x = (s - p(h2) + 1) / (p(h1 + 1) + p(h2 + 1) - 3);
			if (x > 0) {
				ll last = (s - p(h2) + 1) % (p(h1 + 1) + p(h2 + 1) - 3);
				for (int n = 0; n <= h1 + h2; ++n) {
					ll temp = calc(last + n, x, h1, h2, n);
					num += temp;
				}
			}
		}
	}

	cout << num << endl;
	return 0;
}

/*花开二度之时*/