CF750G New Year and Binary Tree Paths（DP）

神仙题。为啥我第一眼看上去以为是个普及题

路径有两种，第一种是从 LCA 一边下去的，第二种是从 LCA 两边都下去了的。

先考虑第一种。

先枚举路径长度 \(h\)。

当 LCA 编号是 \(x\) 时，且所有儿子都是往左走时，和为 \((2^h-1)x\)；所有儿子都往右走时，和为 \((2^h-1)x+2^h-1\)。显然 \((2^h-1)x\le s\le (2^h-1)x+2^h-1\)。

考虑从下往上第 \(i\) 个点从左儿子变成右儿子时（其它不变），总和会增加 \(2^i-1\)。

接下来我们发现无论这条路径长什么样，\(x\) 都等于 \(\lfloor\frac{s}{2^h-1}\rfloor\)。因为当 \(x\) 更小时，即使所有儿子都是往右走的，也没有 \(x\) 取 \(\lfloor\frac{s}{2^h-1}\rfloor\) 时所有儿子都往左走的和大，自然不可能和为 \(s\)。\(x\) 更大时同理。

所以我们想让总和再增加 \(s-(2^h-1)x\)。问题就是有多少种方案，从 \(2^1-1,2^2-1,\dots,2^{h-1}-1\) 中选出一些数（LCA 不能选），使得和为 \(s-(2^h-1)x\)。

这就简单了。枚举选了 \(cnt\) 个数，就是能否从 \(2^1,2^2,\dots,2^{h-1}\) 中选出一些数使得和为 \(s-(2^h-1)x+cnt\)。当且仅当 \(s-(2^h-1)x+cnt\) 中 \(1\) 的个数恰好为 \(cnt\) 方案为 \(1\)，否则为 \(0\)。

接下来考虑第二种。

同样的，枚举左链和右链的长度 \(l\), \(r\)（都包括 LCA，至少我是这么写的）。同理可以推出 \(x\) 恒等于 \(\lfloor\frac{s-2^{r-1}+1}{2^l+2^r-3}\rfloor\)。

同理，考虑从全部是左儿子变成一些右儿子。（当然，LCA 的两个儿子除外）

问题就是有多少种方案，从 \(2^1-1,2^2-1,\dots,2^{l-1}-1,2^1-1,2^2-1,\dots,2^{r-1}-1\) 中选出一些数，使得和为 \(s-2^{r-1}+s-(2^l+2^r-3)x\)。

同样枚举个数 \(cnt\)。下文为了方便设 \(res=s-2^{r-1}+s-(2^l+2^r-3)x+cnt\)。

这回没办法了，老实上 DP。

令 \(f[i][j][k]\) 表示考虑 \(2^1\) 到 \(2^i\) 这些数，从中选出了 \(j\) 个，上一位有没有向这一位进位（\(k\) 是 01 变量）。

初始状态有 \(f[0][0][0]=1\)。要求是 \(f[\max(l,r)][cnt][0]\)。（由于选完之后不能再进位，所以 \(k=0\)，此时 \(i=\max(l,r)\) 会更方便）

转移方程，枚举左子树选不选（设为 \(a\)），右子树选不选（设为 \(b\)），\(f[i+1][j+a+b][\lfloor\frac{k+a+b}{2}\rfloor]+=f[i][j][k]\)。

转移条件，首先对应的数要能选（即 \(i+1\ge l-1\) 时就选不了左子树了），另外 \(res\) 的第 \(i+1\) 位应恰好是 \((k+a+b)\bmod 2\)。

时间复杂度 \(O(\log^5s)\)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=100010,mod=998244353;

#define lson o<<1,l,mid

#define rson o<<1|1,mid+1,r

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

inline int read(){

	int x=0,f=0;char ch=getchar();

	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

	return f?-x:x;

}

ll n,f[55][111][2];

int bitcnt(ll x){

	int c=0;

	for(;x;x&=x-1) c++;

	return c;

}

ll solve1(){

	ll ans=0;

	FOR(i,1,50){

		ll x=n/((1ll<<i)-1);

		if(!x) break;

		ll res=n-x*((1ll<<i)-1);

		FOR(j,0,i-1) if((res+j)%2==0 && bitcnt(res+j)==j) ans++;

	}

	return ans;

}

ll solve2(){

	ll ans=0;

	FOR(l,2,50) FOR(r,2,50){

		ll x=(n-(1ll<<(r-1))+1)/((1ll<<l)+(1ll<<r)-3);

		if(!x) break;

//		printf("x=%lld\n",x);

		ll res=n-(1ll<<(r-1))+1-x*((1ll<<l)+(1ll<<r)-3);

		FOR(cnt,0,l+r-4) if((res+cnt)%2==0){

//			printf("l=%d,r=%d,cnt=%d,res+cnt=%d\n",l,r,cnt,res+cnt);

			FOR(i,0,max(l,r)) FOR(j,0,min(cnt,2*i)) f[i][j][0]=f[i][j][1]=0;

			f[0][0][0]=1;

			FOR(i,1,max(l,r)) FOR(j,0,min(cnt,2*(i-1))){

				FOR(k,0,1) FOR(a,0,1) FOR(b,0,1){

					if(i>=l-1 && a==1) continue;

					if(i>=r-1 && b==1) continue;

					if((k+a+b)%2==((res+cnt)>>i)%2) f[i][j+a+b][(k+a+b)/2]+=f[i-1][j][k];

				}

//				printf("f[%d][%d][0]=%lld,f[%d][%d][1]=%lld\n",i-1,j,f[i-1][j][0],i-1,j,f[i-1][j][1]);

			}

			ans+=f[max(l,r)][cnt][0];

		}

	}

	return ans;

}

int main(){

	scanf("%lld",&n);

	printf("%lld\n",solve1()+solve2());

}

巴特西

CF750G New Year and Binary Tree Paths（DP）

最新文章

热门文章