T15 New Year and Binary Tree Paths (CF750G)

苹果蓝17 · 2020-05-05 11:19:07 · 个人记录

T15 New Year and Binary Tree Paths (CF750G)

很妙的一道题，隐藏的数位dp

CF传送门

洛谷传送门

题意简述

一颗无穷个节点的完全二叉树,编号满足线段树分配，求有多少条树上的简单路径编号和为 s 。

数据范围

1 \leq s \leq 10^{15}

Time:3s

题解

思路

乍看没有什么思路……

仔细一想，一条路径只有两种可能，一条链或是一个分叉（顶点即为 LCA ）

设顶点为链上深度最小的点。如果确定了顶点为 x ，其实有了 s 的限制，可能性也不多了

一条链

设链的长度为 h

假设从 x 往下全走左边，权值和即为

\sum\limits_{i=0}^{h-1} 2^ix = (2^h-1)x \leq s

全走右边呢？

\sum\limits_{i=0}^{h-1} 2^i(x+1)-1 = (2^h-1)(x+1)-h \geq s

只有唯一解 x_0

证明：

当 x=x_0+1 时， (2^h-1)x = (2^h-1)(x_0+1) = s+h >s ，与 (1) 矛盾

当 x=x_0-1 时， (2^h-1)x_0 -h \leq s-h <s，与 (2) 矛盾

所以对于一个确定的深度 h ，顶点 x 是确定的！

但并不是每个 h 都有解

设现在链上的所有节点都在左边，此时和为 base = (2^h-1)x

选出一些节点变成右边

现在来考虑把一个左边的结点变成右边，这个点到链底的深度为 p ，其它相对于父节点位置不变

这样一个变换会带来 \sum\limits_{i=0}^{p-1} 2^ix = (2^p-1)x 的贡献

只要找一些 p 使得贡献和为 ret = s - base 即可

发现 2^i-1 = \sum\limits_{j=0}^{i-1} 2^j > \sum\limits_{j=0}^{j-1} 2^j-1

直接从大到小贪心做即可

ret = s$ % $ (2^h-1)$ , $(s>=2^h-1)

一个分叉 = 两条链

类似的，设顶点为 x

但是为了方便，这次从子节点 2x （深度为 h_1）与 2x+1 （深度为 h_2）开始算深度

还是先都往左走

base = x+2x(2^{h_1}-1)+(2x+1)(2^{h_2}-1)

= x+2^{h_1+1}x-2x+2^{h_2+1}x-2x+2^{h_2}-1

=x(2^{h_1+1}+2^{h_2+1}-3)+2^{h_2}-1

同理仍然可以得到当 h_1 , h_2 确定时，x 也是确定的

这次我们要用 2^1-1, 2^2-1,\dots,2^{h_1}-1,2^1-1,2^2-1,\dots,2^{h_2}-1 来拼凑出 s - base

显然麻烦多了，因为凑出的方法有很多

来转换一下，假设要选出 n 个数来凑，其实就是用 2^1, 2^2,\dots,2^{h_1},2^1,2^2,\dots,2^{h_2} 凑出 ret = s - base + n

可以数位dp！

ret = (s-2^{h_2}+1)$ % $ (2^{h_1+1}+2^{h_2+1}-3)$ , $(s-2^{h_2}+1>=2^{h_1+1}+2^{h_2+1}-3)

做法

数位dp外面要枚举 h_1 , h_2 , n

这里的数位dp其实并不是传统的那种数位dp，只是借用了这个思想

顺序也不是从高往低，而是从低往高

选第 i 个数（ 2^{i+1} ）相当于往第 i+1 位加 1 ，超过了 2 就会进位

所以设 f[i][j][k] 为选到第 i+1 位，共选了 j 个数，上一位是否进到了这一位

当然需要满足 (这一位选择的数量+k)%2==ret的这一位

最后的答案是 f[log2(ret)][n][0] （因为进位就不是这个数了）

注意事项

这题细节也很多

计算2的幂不能直接用位运算（因为ll会溢出），需要预处理
预处理还需要多处理一位，因为后面会用到
计算 x 时要判断 x 存不存在，不存在就 break 掉
算分叉时要特判 ret==0 （不用转移），直接加进答案

为什么？我也不知道

只有当 ret 为偶数时才有解（代码中用 ret + n 代替了）
dp时要注意判断能不能选

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll s,bit[66],cnt,ans,f[66][155][2];
ll dp(ll s,ll tot,ll h1,ll h2){
    memset(f,0,sizeof(f));
    f[0][0][0]=1;//初始化 
    int ed=log2(s);
    for(ll i=1;i<=ed;i++)
        for(ll j=0;j<=i*2-2;j++)//j是之前选过的数的数量 
            for(ll k=0;k<=1;k++)//是否进位 
                for(ll p1=0;p1<=1;p1++){//选不选h1的 
                    if(i>=h1 && p1) break;
                    for(ll p2=0;p2<=1;p2++){//选不选h2的 
                        if(i>=h2 && p2) break;
                        if((p1+p2+k)%2==((s>>i)&1))//转移条件 
                            f[i][j+p1+p2][(p1+p2+k)/2]+=f[i-1][j][k]; 
                    }
                }
    return f[ed][tot][0];
}
int main(){
    scanf("%lld",&s);
    bit[0]=1;
    for(;bit[cnt]<=s;)
        cnt++,bit[cnt]=bit[cnt-1]*2;//预处理2的幂 
    bit[cnt+1]=bit[cnt]*2;//多处理一位 
    for(ll i=1;i<=cnt;i++){//链的情况 
        if(s<(bit[i]-1)) break;//x不存在 
        ll ret=s%(bit[i]-1);
        for(ll j=i;j>=1;j--) if(ret>=bit[j]-1) ret-=bit[j]-1;//贪心 
        if(!ret) ans++;
    }
    for(ll h1=1;h1<=cnt;h1++)
        for(ll h2=1;h2<=cnt;h2++){//枚举h1,h2 
            if((s-bit[h2]+1)<(bit[h1+1]+bit[h2+1]-3)) break;//x不存在 
            ll ret=(s-bit[h2]+1)%(bit[h1+1]+bit[h2+1]-3);
            if(!ret) {ans++; continue;}//特判ret=0 
            for(ll n=1;n<=h1+h2;n++)//枚举n 
                if((ret+n)%2==0)//必须是偶数才有解 
                    ans+=dp(ret+n,n,h1,h2);
            }
    printf("%lld",ans);
}