欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF750G New Year and Binary Tree Paths

程序员文章站 2022-06-22 13:18:06
[TOC] "题目链接" 简单的 设从节点$x$开始不断往左儿子走h 1步,则编号和为$x\sum_{i=0}^{h 1}2^i=x(2^h 1)$。 若倒数第$i$步走向的是右儿子,则编号和会增加$\sum_{j=0}^{i 1}2^j=2^i 1$。 这样,从$x$往下走形成的长为$h$的链中, ......

目录

题目链接

简单的

设从节点\(x\)开始不断往左儿子走h-1步,则编号和为\(x\sum_{i=0}^{h-1}2^i=x(2^h-1)\)

若倒数第\(i\)步走向的是右儿子,则编号和会增加\(\sum_{j=0}^{i-1}2^j=2^i-1\)

这样,从\(x\)往下走形成的长为\(h\)的链中,其中倒数\(i,i\in t\)步时走向右儿子,倒数\(i,i\not\in t\)步走向左儿子,这样得到的编号和为

\[ x(2^h-1)+\sum_{i\in t}2^i-|t|=s \]

\(l=\lfloor\frac{s}{2^h-1}\rfloor\),显然\(|t|<h\le\log_2(s+1),x\le l\)。又因为

\[ (l-1)(2^h-1)+\sum_{i\in t}2^i-|t|\le s-(2^h-1)+(2^h-h-1)\\ =s-h<s \]

\(x>l-1\)进而\(x=l\),或称对每个\(h\)有唯一的\(x=l\),那么方案数为方程\(\sum_{i\in t}2^i=s+|t|+l(2^h-1)\)的解的个数。(这显然最多只有一组解)

组合的

从节点\(x\)的左右儿子出发的两天简单链分别表示为\((h_0,t_0),(h_1,t_1)\),总的编号和

\[ x+2x(2^{h_0}-1)+(2x+1)(2^{h_1}-1)+\sum_{i\in t_0}2^i+\sum_{i\in t_1}2^i-|t_0|-|t_1|\\ =x(2^{h_0+1}+2^{h_1+1}-3)+2^{h_1}-1+\sum_{i\in t_0}2^i+\sum_{i\in t_1}2^i-|t_0|-|t_1|=s \]

大胆猜想\(h_0,h_1\)确定时有唯一的\(x=\lfloor\frac{s-2^{h_1}+1}{2^{h_0+1}+2^{h_1+1}-3}\rfloor\)

接着问题转变为在\({2^1,2^2,\cdots,2^{h_0-1}},{2^1,2^2,\cdots,2^{h_1-1}}\)中一共选取\(n\)个数之和等于\(s-(\cdots)+n\)(qaq)的方案数。

考虑枚举\(n\),设\(f[i,j,0/1]\)表示考虑完前\(i\)个指数后,已经选了\(j\)个数字,这一位(二进制末尾第\(i+1\)位)为是否进位的方案数。其中\(f[0,0,0]=1\)

答案是\(\sum_{h_0,h_1}(\sum_n f[\max(h_0,h_1),n,0])\)。时间复杂度\(o(\log_2^5s)\)

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int n=53;

ll s,l,ans;
ll p[n]={1};
ll f[n][n*2][2];

int main() {
    scanf("%lld",&s); l=log2(s+1);
    for(int i=1; i<n; ++i) p[i]=p[i-1]<<1;
    for(int h=1; h<=l; ++h) {
        ll x=s%(p[h]-1);
        for(int i=h; i; --i) if(x>=p[i]-1) x-=p[i]-1;
        ans+=(!x);
    }
    for(int h0=1; h0<l; ++h0)
    for(int h1=1; s+1-p[h1]>=p[h0+1]+p[h1+1]-3; ++h1) {
        ll x=(s+1-p[h1])/(p[h0+1]+p[h1+1]-3);
        ll r=(s+1-p[h1])%(p[h0+1]+p[h1+1]-3);
        if(!r) {ans++; continue;}
        if(h0==1&&h1==1) {ans+=(s==x*5+1); continue;}
        for(int n=1; n<=h0+h1; ++n) {
            ll c=r+n,l=log2(c);
            if(c&1) continue;
            memset(f[0],0,sizeof f[0]); f[0][0][0]=1;
            for(int i=1; i<=l; ++i) {
                int d=(c>>i)&1; memset(f[i],0,sizeof f[i]);
                for(int j=0; j<=i+i-2&&j<=n; ++j)
                for(int k=0; k<2; ++k) if(f[i-1][j][k]) 
                    for(int x=0; x<2; ++x) if(!x||i<h0)
                    for(int y=0; y<2; ++y) if(!y||i<h1) 
                        if(((k+x+y)&1)==d) f[i][j+x+y][(k+x+y)>>1]+=f[i-1][j][k];
            }
            ans+=f[l][n][0];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

不知道1k+ms是怎么跑出来的