CF750G

· · 题解

题意

一颗无穷个节点的完全二叉树 ，编号满足线段树分配。

求有多少条树上的简单路径编号和为 s 。

1\le s\le10^{15}

题解

1.考虑一条链

考虑从节点 x 开始走的一条节点个数是 h 的链。

假设一直往左子树里走 ，那么他的贡献是：

x\sum_{i=0}^{h-1}2^i=(2^h-1)x

若链从下往上的第 i\in[1,h) 个点是右儿子则会给标号和带来独立的 \displaystyle\sum_{j=0}^{i-1}2^j=2^{i}-1 的贡献。

注意到 x 的取值只能是 \displaystyle\lfloor\frac{s}{2^h-1}\rfloor 。

证明:假设取 x-1 ，这条长 h 的链全部往右子树里走的贡献是：

(2^h-1)(x-1)+\sum_{i=1}^{h-1}2^i-1=2^h-h\le 2^h-1

所以我们可以枚举 h\in[1,\log_2s] ，并算出 x ，令 ret=s- 上面的贡献。

然后我们可以枚举看看能不能把某些点换成右儿子。

即从大到小贪心用 2^{h-1}-1,\ldots,3,1 凑出 ret 。

2.考虑有分叉的情况

假设路径的 lca 是 x ，设从 x 左儿子开始向下的链长度为 h_1 ，从 x 右儿子开始向下的链长度为 h_2 ，枚举 h_1,h_2\in[1,\log_2s] 。

假设这两条链都往左边走的贡献是：

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

同理 x 的位置也是唯一确定的 ，令 ret=s- 上面的贡献。

同样的我们可以考虑怎么用 1,3,\ldots,2^{h_1}-1,1,3,\ldots,2^{h_2}-1 凑出 ret 。

这样显然很难做 ，我们考虑用 2,2^2,\ldots,2^{h_1},2,2^2,\ldots,2^{h_2} 来凑。

我们可以枚举选了 n 个数 ，看看能不能用上面的数凑出 ret+n 。

这个可以用 O(h_1h_2) 的时间用数位 DP 来求出。

3.数位 DP

设 f[i][j][k] 表示前 i+1 位（因为待选数里没有 1 ）选了 j 个数 ，这一位是否进位（ k=1/0 ）的方案数。

对于每一位枚举 2,2^2,\ldots,2^{h_1} 和 2,2^2,\ldots,2^{h_2} 中的这一位填不填。

注意到因为是第 i+1 位如果 i>h_1 那么这一位是不能选 1 的 ，另一边同理。

假设 2,2^2,\ldots,2^{h_1} 中这一位选了 a\in[0,1] ，另外一个选了 b\in[0,1] ，可得转移方程：

f[i+1][j+a+b][\frac{a+b+k}2]=\sum f[i][j][k]

注意转移是要满足 \displaystyle a+b+k\equiv\lfloor\frac{ret+n}{2^i}\rfloor\pmod{2} 的。

具体实现以及卡常可以再看看代码思考一下。

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

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a,i##end=(b)+1;i<i##end;++i)
#define fd(i,a,b) for(int i=a,i##end=(b)-1;i>i##end;--i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=52;
typedef long long ll;
/*-------------------------------------------------------------------------------------*/
int m,p;ll n,ans,mi[N],f[N][2*N][2];
inline ll sub(ll a,ll b){return a>=b?a-b:a;}
inline ll calc(ll s,ll q,int a,int b,int t){
    memset(f[p],0,sizeof f[p]);f[p][0][0]=1;
    fp(i,1,log2(s)+1){
        int d=(s>>i)&1;p^=1;memset(f[p],0,sizeof f[p]);
        fp(j,0,2*i-2)fp(k,0,1)if(f[p^1][j][k])
            fp(x,0,1)if(!x||i<a)fp(y,0,1)if(!y||i<b)
                if((k+x+y)%2==d)f[p][j+x+y][(k+x+y)/2]+=f[p^1][j][k];
    }
    return f[p][t][0];
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    scanf("%lld",&n);mi[0]=1;ll x,ret;
    while(mi[m-1]<=n){mi[m+1]=mi[m]<<1,++m;}--m;
    fp(i,1,m)if((x=n/(mi[i]-1))>0){
        ret=n-x*(mi[i]-1);
        fd(j,i-1,0)ret=sub(ret,mi[j]-1);
        if(!ret)++ans;
    }
    fp(i,1,m)for(int j=1;mi[j]-1<=n;++j)
        if((x=(n-mi[j]+1)/(mi[i+1]+mi[j+1]-3))>0){
            ret=(n-mi[j]+1)-x*(mi[i+1]+mi[j+1]-3);
            if(!ret){++ans;continue;}
            if(i==1&&j==1){ans+=ret==5*x+1;continue;}
            fp(k,1,i+j)if(~(ret+k)&1)
                ans+=calc(ret+k,x,i,j,k);
        }
    printf("%lld",ans);
return 0;
}
{\rm upd}:2020.08.10

修正了一些 \LaTeX 排版错误和题解错误。